login
Triangle T, read by rows, such that row n equals column 0 of matrix power M^n where M is a triangular matrix defined by M(k+m,k) = binomial(k+m,k) for m=0..2 and zeros elsewhere. Width-2-restricted finite functions.
1

%I #33 Jan 05 2021 22:22:23

%S 1,1,1,1,1,2,4,6,6,1,3,9,24,54,90,90,1,4,16,60,204,600,1440,2520,2520,

%T 1,5,25,120,540,2220,8100,25200,63000,113400,113400,1,6,36,210,1170,

%U 6120,29520,128520,491400,1587600,4082400,7484400,7484400,1,7,49,336,2226

%N Triangle T, read by rows, such that row n equals column 0 of matrix power M^n where M is a triangular matrix defined by M(k+m,k) = binomial(k+m,k) for m=0..2 and zeros elsewhere. Width-2-restricted finite functions.

%C T(k,n) is the number of distinct ways in which n labeled objects can be distributed in k labeled urns allowing at most 2 objects to fall in each urn. - _N-E. Fahssi_, Apr 22 2009

%C T(k,n) is the number of functions f:[n]->[k] such that the preimage set under f of any element of [k] has size 2 or less. - _Dennis P. Walsh_, Feb 15 2011

%H Dennis Walsh, <a href="http://frank.mtsu.edu/~dwalsh/WIDTH_2.pdf">Width-restricted finite functions</a>

%H Donghwi Park, <a href="http://arxiv.org/abs/1507.06401">Space-state complexity of Korean chess and Chinese chess</a>, arXiv preprint arXiv:1507.06401, 2015

%F T(k,n) = n!*Sum_{i=ceiling(n/2)..k} binomial(k,i)*binomial(i,n-i)*2^(i-n). - _Dennis P. Walsh_, Feb 15 2011

%F T(n,2*n) = (2n)!/2^n; thus the rightmost border of T equals A000680.

%F Main diagonal (central terms) equals A012244.

%F Other diagonals include A036774 and A003692.

%F Row sums of triangle T equals A003011, the number of permutations of up to n kinds of objects, where each kind of object can occur at most two times.

%F T(k,n) = n![x^n](1+x+x^2/2)^k. Double e.g.f.: Sum_{k,n} T(k,n)*(z^k/k!)*(x^n/n!) = exp(z(1+x+x^2/2)). - _N-E. Fahssi_, Apr 22 2009

%F T(j+k,n) = Sum_{i=0..n} binomial(n,i)*T(j,i)*T(k,n-i). - _Dennis P. Walsh_, Feb 15 2011

%e This triangle T begins:

%e 1;

%e 1, 1, 1;

%e 1, 2, 4, 6, 6;

%e 1, 3, 9, 24, 54, 90, 90;

%e 1, 4, 16, 60, 204, 600, 1440, 2520, 2520;

%e 1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400;

%e 1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400;

%e 1, 7, 49, 336, 2226, 14070, 83790, 463680, 2346120, 10636920, 42071400, 139708800, 366735600, 681080400, 681080400,

%e 1, 8, 64, 504, 3864, 28560, 201600, 1345680, 8401680, 48444480, 254016000, 1187524800, 4819953600, 16345929600, 43589145600, 81729648000, 81729648000,

%e 1, 9, 81, 720, 6264, 52920, 430920, 3356640, 24811920, 172504080, 1116536400, 6646147200, 35835307200, 171632260800, 711047937600, 2451889440000, 6620101488000, 12504636144000, 12504636144000,

%e ...

%e Rows 6 and 8 appear in Park (2015). - _N. J. A. Sloane_, Jan 31 2016

%e Let M be the triangular matrix that begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 0, 3, 3, 1;

%e 0, 0, 6, 4, 1;

%e 0, 0, 0, 10, 5, 1; ...

%e where M(k+m,k) = C(k+m,k) for m=0,1,2 and zeros elsewhere.

%e Illustrate that row n of T = column 0 of M^n for n >= 0 as follows.

%e The matrix square M^2 begins:

%e 1;

%e 2, 1;

%e 4, 4, 1;

%e 6, 12, 6, 1;

%e 6, 24, 24, 8, 1;

%e 0, 30, 60, 40, 10, 1; ...

%e with column 0 of M^2 forming row 2 of T.

%e The matrix cube M^3 begins:

%e 1;

%e 3, 1;

%e 9, 6, 1;

%e 24, 27, 9, 1;

%e 54, 96, 54, 12, 1;

%e 90, 270, 240, 90, 15, 1;

%e 90, 540, 810, 480, 135, 18, 1; ...

%e with column 0 of M^3 forming row 3 of T.

%e T(2,3)=6 because there are 6 ways to lodge 3 distinguishable balls, labeled by numbers 1,2 and 3, in 2 distinguishable boxes, each of which can hold at most 2 balls. - _N-E. Fahssi_, Apr 22 2009

%e T(5,8)=63000 because there are 63000 ways to assign 8 students to a dorm room when there are 5 different two-bed dorm rooms that are available. (See link for details of the count.) - _Dennis P. Walsh_, Feb 15 2011

%p seq(seq(n!*sum(binomial(k,j)*binomial(j,n-j)*2^(j-n),j=ceil(n/2)..k),n=0..2*k),k=1..10); # _Dennis P. Walsh_, Feb 15 2011

%t T[k_, n_] := If[n == 0, 1, n! Coefficient[(1 + x + x^2/2)^k, x^n]]; TableForm[Table[T[k, n], {k, 0, 10}, {n, 0, 2 k}]] (* _N-E. Fahssi_, Apr 22 2009 *)

%o (PARI) {T(n,k)=local(M=matrix(n+1,n+1,n,k,if(n>=k,if(n-k<=2,binomial(n-1,k-1))))); if(k>2*n,0,(M^n)[k+1,1])}

%Y Cf. A003011 (row sums), A000680 (right border); diagonals: A012244, A036774, A003692.

%K nonn,tabf

%O 0,6

%A _Paul D. Hanna_, Jul 28 2008