OFFSET
0,13
COMMENTS
Arndt and Sloane (see the link and A278984) identify the sequence to give "the number of words of length n over an alphabet of size b that are in standard order" and provide the formula Sum_{j = 1..b} Stirling_2(n, j) assuming b >= 1 and j >= 1. Compared to the array as defined here this misses the first row and the first column of our array.
The method used here is the special case of a general method described in A320956 applied to the function exp. For applications to other functions see the cross references.
A(k,n) is the number of color patterns (set partitions) for an oriented row of length n using up to k colors (subsets). Two color patterns are equivalent if the colors are permuted. For A(3,4) = 14, the six achiral patterns are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA; the eight chiral patterns are the four chiral pairs AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - Robert A. Russell, Nov 10 2018
LINKS
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
FORMULA
A(n, k) = (1/n!)*Sum_{j=0..n-1} A008290(n, n-j)*(n-j)^k if k > 0.
If one drops the special case A(n, 0) = 1 from the definition then column 0 becomes Sum_{k=0..n} (-1)^k/k! = A103816(n)/A053556(n).
Row n is given for k >= 1 by a_n(k), where
a_0(k) = 0^k/0!.
a_1(k) = 1^k/1!.
a_2(k) = (2^k)/2!.
a_3(k) = (3^k + 3)/3!.
a_4(k) = (6*2^k + 4^k + 8)/4!.
a_5(k) = (20*2^k + 10*3^k + 5^k + 45)/5!.
a_6(k) = (135*2^k + 40*3^k + 15*4^k + 6^k + 264)/6!.
a_7(k) = (924*2^k + 315*3^k + 70*4^k + 21*5^k + 7^k + 1855)/7!.
a_8(k) = (7420*2^k + 2464*3^k + 630*4^k + 112*5^k + 28*6^k + 8^k + 14832)/8!.
Note that the coefficients of the generating functions a_n are the recontres numbers A000240, A000387, A000449, ...
Rewriting the formulas with exponential generating functions for the rows we have egf(n) = Sum_{k=0..n} !k*binomial(n,k)*exp(x*(n-k)) and A(n, k) = (k!/n!)*[x^k] egf(n). In this formulation no special rule for the case k = 0 is needed.
The rows converge to the Bell numbers. Convergence here means that for every fixed k the terms in column k differ from A000110(k) only for finitely many indices.
A(n, n) are the Bell numbers A000110(n) for n >= 0.
EXAMPLE
Array starts:
n\k 0 1 2 3 4 5 6 7 8 9 ...
----------------------------------------------------
[0] 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... A000007
[1] 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A000012
[2] 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, ... A011782
[3] 1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281, ... A124302
[4] 1, 1, 2, 5, 15, 51, 187, 715, 2795, 11051, ... A124303
[5] 1, 1, 2, 5, 15, 52, 202, 855, 3845, 18002, ... A056272
[7] 1, 1, 2, 5, 15, 52, 203, 877, 4139, 21110, ...
[8] 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21146, ...
[9] 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, ...
----------------------------------------------------
Seen as a triangle given by the descending antidiagonals:
[0] 1
[1] 0, 1
[2] 0, 1, 1
[3] 0, 1, 1, 1
[4] 0, 1, 2, 1, 1
[5] 0, 1, 4, 2, 1, 1
[6] 0, 1, 8, 5, 2, 1, 1
[7] 0, 1, 16, 14, 5, 2, 1, 1
MAPLE
A := (n, k) -> if k = 0 then 1 else add(A008290(n, n-j)*(n-j)^k, j=0..n-1)/n! fi:
seq(lprint(seq(A(n, k), k=0..9)), n=0..9); # Prints the array row-wise.
seq(seq(A(n-k, k), k=0..n), n=0..11); # Gives the array as listed.
MATHEMATICA
T[n_, 0] := 1; T[n_, k_] := Sum[(Subfactorial[j]/Factorial[j])((n - j)^k/(n - j)!), {j, 0, n - 1}]; Table[T[n - k, k], {n, 0, 11}, {k, 0, n}] // Flatten
Table[Sum[StirlingS2[k, j], {j, 0, n-k}], {n, 0, 11}, {k, 0, n}] // Flatten (* Robert A. Russell, Nov 10 2018 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Nov 05 2018
STATUS
approved