A140735 - OEIS

A140735

Triangle read by rows, X^n * [1,0,0,0,...]; where X = a tridiagonal matrix with (1,2,3,...) in the main diagonal and (1,1,1,...) in the sub and subsubdiagonals.

1, 1, 1, 1, 1, 3, 5, 2, 1, 1, 7, 19, 16, 12, 3, 1, 1, 15, 65, 90, 95, 46, 22, 4, 1, 1, 31, 211, 440, 630, 461, 295, 100, 35, 5, 1, 1, 63, 665, 2002, 3801, 3836, 3156, 1556, 710, 185, 51, 6, 1, 1, 127, 2059, 8736, 21672, 28819, 29729, 19440, 11102, 4116, 1456, 308, 70

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

T(m,k) is the number of achiral color patterns in a row or loop of length 2m-1 using exactly k different colors. Two color patterns are equivalent if we permute the colors. - Robert A. Russell, Mar 24 2018

LINKS

Table of n, a(n) for n=1..62.

MathOverflow, What is the number of achiral color patterns for a row of n colors containing k different colors?

FORMULA

G.f.(exponential in x, ordinary in t): exp(x+t*(exp(x)-1)+(1/2)*t^2*(exp(2*x)-1)). - Ira M. Gessel, Jan 30 2018

T(m,k) = [m>1]*(k*T(m-1,k)+T(m-1,k-1)+T(m-1,k-2)) + [m==1]*[k==1] - Robert A. Russell, Apr 24 2018

EXAMPLE

First few rows of the triangle are:

1, 1, 1;

1, 3, 5, 2, 1;

1, 7, 19, 16, 12, 3, 1;

1, 15, 65, 90, 95, 46, 22, 4, 1;

1, 31, 211, 440, 630, 461, 295, 100, 35, 5, 1;

1, 63, 665, 2002, 3801, 3836, 3156, 1556, 710, 185, 51, 6, 1;

...

T(3,3)=5 is the number of achiral color patterns of length five using exactly three colors. These are AABCC, ABACA, ABBBC, ABCAB, and ABCBA for both rows and loops. - Robert A. Russell, Mar 24 2018

MATHEMATICA

(* Ach[n, k] is the number of achiral color patterns for a row or loop of n

colors containing k different colors *)

Ach[n_, k_] := Ach[n, k] = Which[0==k, Boole[0==n], 1==k, Boole[n>0],

OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],

True, Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]

+ 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]

Table[Ach[n, k], {n, 1, 13, 2}, {k, 1, n}] // Flatten

(* Robert A. Russell, Feb 06 2018 *)

Table[MatrixPower[Table[Switch[j-i, 0, i, 1, 1, 2, 1, _, 0],

{i, 1, 2 n - 1}, {j, 1, 2 n - 1}], n-1][[1]], {n, 1, 10}]

// Flatten (* Robert A. Russell, Mar 24 2018 *)