login
T(n,k) = number of arrays of n 0..k integers with new values introduced in order 0..k but otherwise unconstrained. Array read by antidiagonals.
9

%I #23 Jul 06 2024 12:22:55

%S 1,1,2,1,2,4,1,2,5,8,1,2,5,14,16,1,2,5,15,41,32,1,2,5,15,51,122,64,1,

%T 2,5,15,52,187,365,128,1,2,5,15,52,202,715,1094,256,1,2,5,15,52,203,

%U 855,2795,3281,512,1,2,5,15,52,203,876,3845,11051,9842,1024,1,2,5,15,52,203,877

%N T(n,k) = number of arrays of n 0..k integers with new values introduced in order 0..k but otherwise unconstrained. Array read by antidiagonals.

%C Table starts

%C ....1.....1......1......1......1......1......1......1......1......1......1

%C ....2.....2......2......2......2......2......2......2......2......2......2

%C ....4.....5......5......5......5......5......5......5......5......5......5

%C ....8....14.....15.....15.....15.....15.....15.....15.....15.....15.....15

%C ...16....41.....51.....52.....52.....52.....52.....52.....52.....52.....52

%C ...32...122....187....202....203....203....203....203....203....203....203

%C ...64...365....715....855....876....877....877....877....877....877....877

%C ..128..1094...2795...3845...4111...4139...4140...4140...4140...4140...4140

%C ..256..3281..11051..18002..20648..21110..21146..21147..21147..21147..21147

%C ..512..9842..43947..86472.109299.115179.115929.115974.115975.115975.115975

%C .1024.29525.175275.422005.601492.665479.677359.678514.678569.678570.678570

%C Lower left triangular part seems to be A102661. - _R. J. Mathar_, Nov 29 2015

%H R. H. Hardin, <a href="/A203647/b203647.txt">Table of n, a(n) for n = 1..10011</a>

%F T(n,k) = Sum_{j = 1..k+1} Stirling2(n,j). - _Andrew Howroyd_, Mar 19 2017

%F T(n,k) = A278984(k+1, n). - _Andrew Howroyd_, Mar 19 2017

%F Empirical for column k:

%F k=1: a(n) = 2*a(n-1)

%F k=2: a(n) = 4*a(n-1) -3*a(n-2)

%F k=3: a(n) = 7*a(n-1) -14*a(n-2) +8*a(n-3)

%F k=4: a(n) = 11*a(n-1) -41*a(n-2) +61*a(n-3) -30*a(n-4)

%F k=5: a(n) = 16*a(n-1) -95*a(n-2) +260*a(n-3) -324*a(n-4) +144*a(n-5)

%F k=6: a(n) = 22*a(n-1) -190*a(n-2) +820*a(n-3) -1849*a(n-4) +2038*a(n-5) -840*a(n-6)

%F k=7: a(n) = 29*a(n-1) -343*a(n-2) +2135*a(n-3) -7504*a(n-4) +14756*a(n-5) -14832*a(n-6) +5760*a(n-7)

%F k=8: a(n) = 37*a(n-1) -574*a(n-2) +4858*a(n-3) -24409*a(n-4) +74053*a(n-5) -131256*a(n-6) +122652*a(n-7) -45360*a(n-8)

%F k=9: a(n) = 46*a(n-1) -906*a(n-2) +9996*a(n-3) -67809*a(n-4) +291774*a(n-5) -790964*a(n-6) +1290824*a(n-7) -1136160*a(n-8) +403200*a(n-9)

%F k=10: a(n) = 56*a(n-1) -1365*a(n-2) +19020*a(n-3) -167223*a(n-4) +965328*a(n-5) -3686255*a(n-6) +9133180*a(n-7) -13926276*a(n-8) +11655216*a(n-9) -3991680*a(n-10)

%F k=11: a(n) = 67*a(n-1) -1980*a(n-2) +33990*a(n-3) -375573*a(n-4) +2795331*a(n-5) -14241590*a(n-6) +49412660*a(n-7) -113667576*a(n-8) +163671552*a(n-9) -131172480*a(n-10) +43545600*a(n-11)

%F k=12: a(n) = 79*a(n-1) -2783*a(n-2) +57695*a(n-3) -782133*a(n-4) +7284057*a(n-5) -47627789*a(n-6) +219409685*a(n-7) -703202566*a(n-8) +1519272964*a(n-9) -2082477528*a(n-10) +1606986720*a(n-11) -518918400*a(n-12)

%F k=13: a(n) = 92*a(n-1) -3809*a(n-2) +93808*a(n-3) -1530243*a(n-4) +17419116*a(n-5) -141963107*a(n-6) +835933384*a(n-7) -3542188936*a(n-8) +10614910592*a(n-9) -21727767984*a(n-10) +28528276608*a(n-11) -21289201920*a(n-12) +6706022400*a(n-13)

%F k=14: a(n) = 106*a(n-1) -5096*a(n-2) +147056*a(n-3) -2840838*a(n-4) +38786748*a(n-5) -385081268*a(n-6) +2816490248*a(n-7) -15200266081*a(n-8) +59999485546*a(n-9) -169679309436*a(n-10) +331303013496*a(n-11) -418753514880*a(n-12) +303268406400*a(n-13) -93405312000*a(n-14)

%F k=15: a(n) = 121*a(n-1) -6685*a(n-2) +223405*a(n-3) -5042947*a(n-4) +81308227*a(n-5) -965408015*a(n-6) +8576039615*a(n-7) -57312583328*a(n-8) +287212533608*a(n-9) -1066335473840*a(n-10) +2866534951280*a(n-11) -5367984964224*a(n-12) +6557974412544*a(n-13) -4622628648960*a(n-14) +1394852659200*a(n-15)

%F From _Robert Israel_, May 20 2016: (Start)

%F T(n,k) = 1 + Sum_{j=1..n-1} binomial(n-1,j-1)*T(n-j,k-1).

%F G.f. for columns g_k(z) satisfies g_k(z) = (z/(1-z))*(1+ g_{k-1}(z/(1-z))) with g_1(z) = z/(1-2z).

%F Thus g_k is a rational function: it has a simple pole at z=1/j for 1<=j<=k+1 except j=k, and it has a finite limit at infinity (so the degree of the numerator is k). This implies that column k satisfies the recurrences listed above, whose coefficients correspond to the expansion of (z-1/(k+1))* Product_{j=1..k-1}(z - 1/j).

%F (End)

%e Some solutions for n=7, k=5:

%e ..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0

%e ..0....0....1....1....1....1....0....0....1....1....1....1....1....1....1....1

%e ..1....0....2....1....2....2....1....1....2....2....2....2....1....2....1....2

%e ..0....1....1....0....3....3....2....2....1....3....1....1....1....0....0....2

%e ..0....0....3....1....0....4....3....0....2....3....1....1....1....0....2....1

%e ..2....2....4....2....2....0....4....2....0....2....2....3....2....3....2....0

%e ..1....3....1....0....2....5....0....0....0....0....0....2....2....1....1....1

%p T:= proc(n,k) option remember; if k = 1 then 2^(n-1)

%p else 1 + add(binomial(n-1,j-1)*procname(n-j,k-1),j=1..n-1)

%p fi

%p end proc:

%p seq(seq(T(k,m-k),k=1..m-1),m=2..10); # _Robert Israel_, May 20 2016

%t T[n_, k_] := Sum[StirlingS2[n, j], {j, 1, k+1}]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Oct 31 2017, after _Andrew Howroyd_ *)

%Y Column 1 is A000079(n-1).

%Y Column 2 is A007051(n-1).

%Y Column 3 is A007581(n-1).

%Y Column 4 is A056272.

%Y Column 5 is A056273.

%Y Column 6 is A099262.

%Y Column 7 is A099263.

%Y Column 8 is A164863.

%Y Column 9 is A164864.

%Y Column 10 is A203641.

%Y Column 11 is A203642.

%Y Column 12 is A203643.

%Y Column 13 is A203644.

%Y Column 14 is A203645.

%Y Column 15 is A203646.

%Y Diagonal is A000110.

%K nonn,tabl

%O 1,3

%A _R. H. Hardin_, Jan 04 2012