A203647 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.

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, 2, 5, 15, 52, 187, 365, 128, 1, 2, 5, 15, 52, 202, 715, 1094, 256, 1, 2, 5, 15, 52, 203, 855, 2795, 3281, 512, 1, 2, 5, 15, 52, 203, 876, 3845, 11051, 9842, 1024, 1, 2, 5, 15, 52, 203, 877

Offset

1,3

Comments

Table starts

....1.....1......1......1......1......1......1......1......1......1......1

....2.....2......2......2......2......2......2......2......2......2......2

....4.....5......5......5......5......5......5......5......5......5......5

....8....14.....15.....15.....15.....15.....15.....15.....15.....15.....15

...16....41.....51.....52.....52.....52.....52.....52.....52.....52.....52

...32...122....187....202....203....203....203....203....203....203....203

...64...365....715....855....876....877....877....877....877....877....877

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

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

..512..9842..43947..86472.109299.115179.115929.115974.115975.115975.115975

.1024.29525.175275.422005.601492.665479.677359.678514.678569.678570.678570

Lower left triangular part seems to be A102661. - R. J. Mathar, Nov 29 2015

Links

R. H. Hardin, Table of n, a(n) for n = 1..10011

Formula

T(n,k) = Sum_{j = 1..k+1} Stirling2(n,j). - Andrew Howroyd, Mar 19 2017

T(n,k) = A278984(k+1, n). - Andrew Howroyd, Mar 19 2017

Empirical for column k:

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

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

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

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

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

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

From Robert Israel, May 20 2016: (Start)

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

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).

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).

(End)

Example

Some solutions for n=7, k=5:
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..0....0....1....1....1....1....0....0....1....1....1....1....1....1....1....1
..1....0....2....1....2....2....1....1....2....2....2....2....1....2....1....2
..0....1....1....0....3....3....2....2....1....3....1....1....1....0....0....2
..0....0....3....1....0....4....3....0....2....3....1....1....1....0....2....1
..2....2....4....2....2....0....4....2....0....2....2....3....2....3....2....0
..1....3....1....0....2....5....0....0....0....0....0....2....2....1....1....1

Maple

T:= proc(n, k) option remember;  if k = 1 then 2^(n-1)
else 1 + add(binomial(n-1, j-1)*procname(n-j, k-1), j=1..n-1)
fi
end proc:
seq(seq(T(k, m-k), k=1..m-1), m=2..10); # Robert Israel, May 20 2016

Mathematica

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 *)

Crossrefs

Column 1 is A000079(n-1).

Column 2 is A007051(n-1).

Column 3 is A007581(n-1).

Column 4 is A056272.

Column 5 is A056273.

Column 6 is A099262.

Column 7 is A099263.

Column 8 is A164863.

Column 9 is A164864.

Diagonal is A000110.

Sequence in context: A035015 A212829 A210215 * A114791 A129994 A208755

Adjacent sequences: A203644 A203645 A203646 * A203648 A203649 A203650

Keyword

nonn,tabl

Author

R. H. Hardin, Jan 04 2012

Status

approved