login
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.
11

%I #41 Apr 24 2018 17:18:46

%S 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,

%T 440,630,461,295,100,35,5,1,1,63,665,2002,3801,3836,3156,1556,710,185,

%U 51,6,1,1,127,2059,8736,21672,28819,29729,19440,11102,4116,1456,308,70

%N 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.

%C 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

%H MathOverflow, <a href="https://mathoverflow.net/q/291714">What is the number of achiral color patterns for a row of n colors containing k different colors?</a>

%F 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

%F 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

%e First few rows of the triangle are:

%e 1;

%e 1, 1, 1;

%e 1, 3, 5, 2, 1;

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

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

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

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

%e ...

%e 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

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

%t colors containing k different colors *)

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

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

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

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

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

%t (* _Robert A. Russell_, Feb 06 2018 *)

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

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

%t // Flatten (* _Robert A. Russell_, Mar 24 2018 *)

%t Aodd[m_, k_] := Aodd[m, k] = If[m > 1, k Aodd[m-1, k] + Aodd[m-1, k-1]

%t + Aodd[m-1, k-2], Boole[m==1 && k==1]]

%t Table[Aodd[m,k],{m,1,10},{k,1,2m-1}] // Flatten (* _Robert A. Russell_, Apr 24 2018 *)

%Y Cf. A080337 (row sums), A140733, A140744.

%Y Number of achiral color patterns of length even n in A293181.

%K nonn,tabf

%O 1,6

%A _Gary W. Adamson_, May 25 2008