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

Author

R. H. Hardin, Jan 04 2012

Keywords

• nonn
• tabl

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

Examples

			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
		

Links

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

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.

Column 10 is A203641.

Column 11 is A203642.

Column 12 is A203643.

Column 13 is A203644.

Column 14 is A203645.

Column 15 is A203646.

Diagonal is A000110.

Programs

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

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) [phone]*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) [phone]*a(n-7) -113667576*a(n-8) [phone]*a(n-9) -131172480*a(n-10) [phone]*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) [phone]*a(n-7) -703202566*a(n-8) [phone]*a(n-9) -2082477528*a(n-10) [phone]*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) [phone]*a(n-5) -141963107*a(n-6) [phone]*a(n-7) -3542188936*a(n-8) [phone]*a(n-9) -21727767984*a(n-10) [phone]*a(n-11) -21289201920*a(n-12) [phone]*a(n-13)

k=14: a(n) = 106*a(n-1) -5096*a(n-2) +147056*a(n-3) -2840838*a(n-4) [phone]*a(n-5) -385081268*a(n-6) [phone]*a(n-7) -15200266081*a(n-8) [phone]*a(n-9) -169679309436*a(n-10) [phone]*a(n-11) -418753514880*a(n-12) [phone]*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) [phone]*a(n-5) -965408015*a(n-6) [phone]*a(n-7) -57312583328*a(n-8) [phone]*a(n-9) -1066335473840*a(n-10) [phone]*a(n-11) -5367984964224*a(n-12) [phone]*a(n-13) -4622628648960*a(n-14) [phone]*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)