login
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.
9
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
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.
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.
Sequence in context: A035015 A212829 A210215 * A376826 A114791 A129994
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Jan 04 2012
STATUS
approved