A102661 Triangle of partial sums of Stirling numbers of 2nd kind (A008277): T(n,k) = Sum_{i=1..k} Stirling2(n,i), 1<=k<=n.

1, 1, 2, 1, 4, 5, 1, 8, 14, 15, 1, 16, 41, 51, 52, 1, 32, 122, 187, 202, 203, 1, 64, 365, 715, 855, 876, 877, 1, 128, 1094, 2795, 3845, 4111, 4139, 4140, 1, 256, 3281, 11051, 18002, 20648, 21110, 21146, 21147, 1, 512, 9842, 43947, 86472, 109299, 115179, 115929, 115974, 115975

Offset: 1

Author

Vladeta Jovovic, Feb 03 2005

Keywords

• easy
• nonn
• tabl

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

Examples

			Triangle begins:
  1;
  1,  2;
  1,  4,  5;
  1,  8, 14, 15;
  1, 16, 41, 51, 52;
  ...
		

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

Crossrefs

Cf. A000110, A008277, A008949, A048993, A049444.

Cf. A369950, A381682, A381683.

Programs

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

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

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

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