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,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

Cf. A000110, A008949, A048993, A049444.

Sequence in context: A248670 A080935 A362926 * A121574 A117317 A124237

Adjacent sequences: A102658 A102659 A102660 * A102662 A102663 A102664

Keyword

easy,nonn,tabl

Author

Vladeta Jovovic, Feb 03 2005

Status

approved