OFFSET
1,3
COMMENTS
T(n,k) is the number of ways to place n distinguishable balls into k indistinguishable bins. - Geoffrey Critzer, Mar 22 2011
From Mark Wildon, Aug 10 2015: (Start)
T(n,k) is the number of partitions of a set of size n into at most k parts.
T(n,k) is the number of sequences of n top-to-random shuffles of a deck of k cards that leave the deck invariant.
T(n,k) = <pi^n, 1_{Sym_k}> where pi is the natural permutation character of the symmetric group Sym_k. This gives another combinatorial interpretation of T(n,k) as counting sequences of box moves on Young diagrams. Reference linked to below. (End)
Diagonal entries T(n,n) are the Bell numbers A000110. - Robert Israel, Aug 10 2015
REFERENCES
Richard Stanley, Enumerative Combinatorics, Cambridge Univ. Press, 1997 page 38. (#7 of the twelvefold ways)
LINKS
Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
OEIS Wiki, Sorting numbers
FORMULA
E.g.f. for row polynomials s(n,y) = Sum_{k=0..n} a(n,k)*y^k is (y*e^(e^(x*y)-1)- e^(y*(e^x-1)))/(y-1) - 1. - Robert Israel, Aug 10 2015
EXAMPLE
Triangle begins:
1;
1, 2;
1, 4, 5;
1, 8, 14, 15;
1, 16, 41, 51, 52;
...
MAPLE
with(combinat): A102661_row := proc(n) local k, j; seq(add(stirling2(n, j), j=1..k), k=1..n) end:
seq(print(A102661_row(r)), r=1..6); # Peter Luschny, Sep 30 2011
MATHEMATICA
Table[Table[Sum[StirlingS2[n, i], {i, 1, k}], {k, 1, n}], {n, 1, 10}] // Grid (* Geoffrey Critzer, Mar 22 2011*)
Table[Accumulate[StirlingS2[n, Range[n]]], {n, 10}]//Flatten (* Harvey P. Dale, Oct 28 2019 *)
PROG
(Haskell)
a102661 n k = a102661_tabl !! (n-1) !! (k-1)
a102661_row n = a102661_tabl !! (n-1)
a102661_tabl = map (scanl1 (+) . tail) $ tail a048993_tabl
-- Reinhard Zumkeller, Jun 19 2015
(PARI) tabl(nn) = {for (n=1, nn, for (k=1, n, print1(sum(i=1, k, stirling(n, i, 2)), ", "); ); print(); ); } \\ Michel Marcus, Aug 10 2015
(Sage)
def T(n, k):
return sum([stirling_number2(n, j) for j in range(1, k+1)])
# Danny Rorabaugh, Oct 13 2015
CROSSREFS
KEYWORD
AUTHOR
Vladeta Jovovic, Feb 03 2005
STATUS
approved