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
From Manfred Boergens, Mar 18 2025: (Start)
The partitions in the second comment can be described as disjoint collections of subsets of [n] without the empty set with union = [n]. For instance, T(4,2)=8 is the number of partitions of [4] into 1 or 2 parts: 1234, 1 234, 2 134, 3 124, 4 123, 12 34, 13 24, 14 23.
For disjoint collections which may include one empty set see A381682.
For arbitrary collections without the empty set see A369950.
For arbitrary collections which may include one empty set see A381683. (End)
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
(SageMath)
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