A102661 - OEIS

%I #50 Jun 13 2023 07:57:46

%S 1,1,2,1,4,5,1,8,14,15,1,16,41,51,52,1,32,122,187,202,203,1,64,365,

%T 715,855,876,877,1,128,1094,2795,3845,4111,4139,4140,1,256,3281,11051,

%U 18002,20648,21110,21146,21147,1,512,9842,43947,86472,109299,115179,115929,115974,115975

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

%C T(n,k) is the number of ways to place n distinguishable balls into k indistinguishable bins. - _Geoffrey Critzer_, Mar 22 2011

%C From _Mark Wildon_, Aug 10 2015: (Start)

%C T(n,k) is the number of partitions of a set of size n into at most k parts.

%C 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.

%C 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)

%C Diagonal entries T(n,n) are the Bell numbers A000110. - _Robert Israel_, Aug 10 2015

%D Richard Stanley, Enumerative Combinatorics, Cambridge Univ. Press, 1997 page 38. (#7 of the twelvefold ways)

%H Reinhard Zumkeller, <a href="/A102661/b102661.txt">Rows n = 1..125 of triangle, flattened</a>

%H John R. Britnell and Mark Wildon, <a href="http://arxiv.org/abs/1507.04803">Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D</a>, arXiv:1507.04803 [math.CO], 2015.

%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

%H OEIS Wiki, <a href="http://oeis.org/wiki/Sorting_numbers">Sorting numbers</a>

%F 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

%e Triangle begins:

%e   1;

%e   1,  2;

%e   1,  4,  5;

%e   1,  8, 14, 15;

%e   1, 16, 41, 51, 52;

%e   ...

%p with(combinat): A102661_row := proc(n) local k,j; seq(add(stirling2(n,j),j=1..k),k=1..n) end:

%p seq(print(A102661_row(r)),r=1..6); # _Peter Luschny_, Sep 30 2011

%t Table[Table[Sum[StirlingS2[n, i], {i, 1, k}], {k, 1, n}], {n, 1,10}] // Grid (* _Geoffrey Critzer_, Mar 22 2011*)

%t Table[Accumulate[StirlingS2[n,Range[n]]],{n,10}]//Flatten (* _Harvey P. Dale_, Oct 28 2019 *)

%o (Haskell)

%o a102661 n k = a102661_tabl !! (n-1) !! (k-1)

%o a102661_row n = a102661_tabl !! (n-1)

%o a102661_tabl = map (scanl1 (+) . tail) $ tail a048993_tabl

%o -- _Reinhard Zumkeller_, Jun 19 2015

%o (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

%o (Sage)

%o def T(n,k):

%o     return sum([stirling_number2(n,j) for j in range(1,k+1)])

%o # _Danny Rorabaugh_, Oct 13 2015

%Y Cf. A000110, A008949, A048993, A049444.

%K easy,nonn,tabl

%O 1,3

%A _Vladeta Jovovic_, Feb 03 2005