A048993 Triangle of Stirling numbers of 2nd kind, S(n,k), n >= 0, 0 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 7, 6, 1, 0, 1, 15, 25, 10, 1, 0, 1, 31, 90, 65, 15, 1, 0, 1, 63, 301, 350, 140, 21, 1, 0, 1, 127, 966, 1701, 1050, 266, 28, 1, 0, 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1, 0, 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1

Offset: 0

Author

N. J. A. Sloane, Dec 11 1999

Keywords

• nonn
• tabl
• nice

Comments

Also known as Stirling set numbers.

S(n,k) enumerates partitions of an n-set into k nonempty subsets.

The o.g.f. for the sequence of diagonal k (k=0 for the main diagonal) is G(k,x) = ((x^k)/(1-x)^(2*k+1))*Sum_{m=0..k-1} A008517(k,m+1)*x^m. A008517 is the second-order Eulerian triangle. - Wolfdieter Lang, Oct 14 2005

From Philippe Deléham, Nov 14 2007: (Start)

Sum_{k=0..n} S(n,k)*x^k = B_n(x), where B_n(x) = Bell polynomials.

The first few Bell polynomials are:

B_0(x) = 1;

B_1(x) = 0 + x;

B_2(x) = 0 + x + x^2;

B_3(x) = 0 + x + 3x^2 + x^3;

B_4(x) = 0 + x + 7x^2 + 6x^3 + x^4;

B_5(x) = 0 + x + 15x^2 + 25x^3 + 10x^4 + x^5;

B_6(x) = 0 + x + 31x^2 + 90x^3 + 65x^4 + 15x^5 + x^6;

(End)

This is the Sheffer triangle (1, exp(x) - 1), an exponential (binomial) convolution triangle. The a-sequence is given by A006232/A006233 (Cauchy sequence). The z-sequence is the zero sequence. See the link under A006232 for the definition and use of these sequences. The row sums give A000110 (Bell), and the alternating row sums give A000587 (see the Philippe Deléham formulas and crossreferences below). - Wolfdieter Lang, Oct 16 2014

Also the inverse Bell transform of the factorial numbers (A000142). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015

From Wolfdieter Lang, Feb 21 2017: (Start)

The transposed (trans) of this lower triagonal Sheffer matrix of the associated type S = (1, exp(x) - 1) (taken as N X N matrix for arbitrarily large N) provides the transition matrix from the basis {x^n/n!}, n >= 0, to the basis {y^n/n!}, n >= 0, with y^n/n! = Sum_{m>=n} S^{trans}(n, m) x^m/m! = Sum_{m>=0} x^m/m!*S(m, n).

The Sheffer transform with S = (g, f) of a sequence {a_n} to {b_n} for n >= 0, in matrix notation vec(b) = S vec(a), satisfies, with e.g.f.s A and B, B(x) = g(x)*A(f(x)) and B(x) = A(y(x)) identically, with vec(xhat) = S^{trans,-1} vec(yhat) in symbolic notation with vec(xhat)_n = x^n/n! (similarly for vec(yhat)).

(End)

For k >= 1 S(n, k) = h^{(k)}{n-k}, the complete homogeneous symmetric function of the k symbols 1,2, ..., k, of degree n-k. Thus S(n, k) is for k >= 1 the (dimensionless) volume of the multichoose(k, n-k) = binomial(n-1, k-1) polytopes of dimension n-k with (dimensionless) side lengths from the set {1, 2, ..., k}. See an example below. - _Wolfdieter Lang, May 26 2017

Number of partitions of {1, 2, ..., n+1} into k+1 nonempty subsets such that no subset contains two adjacent numbers. - Thomas Anton, Sep 26 2022

Examples

			The triangle S(n,k) begins:
  n\k 0 1    2     3      4       5       6      7      8     9   10 11 12
  0:  1
  1:  0 1
  2:  0 1    1
  3:  0 1    3     1
  4:  0 1    7     6      1
  5:  0 1   15    25     10       1
  6:  0 1   31    90     65      15       1
  7:  0 1   63   301    350     140      21      1
  8:  0 1  127   966   1701    1050     266     28      1
  9:  0 1  255  3025   7770    6951    2646    462     36     1
 10:  0 1  511  9330  34105   42525   22827   5880    750    45    1
 11:  0 1 1023 28501 145750  246730  179487  63987  11880  1155   55  1
 12:  0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66  1
 ... reformatted and extended - _Wolfdieter Lang_, Oct 16 2014
Completely symmetric function S(4, 2) = h^{(2)}_2 = 1^2 + 2^2 + 1^1*2^1 = 7; S(5, 2) = h^{(2)}_3 = 1^3 + 2^3 + 1^2*2^1 + 1^1*2^2 = 15. - _Wolfdieter Lang_, May 26 2017
From _Wolfdieter Lang_, Aug 11 2017: (Start)
Recurrence: S(5, 3) = S(4, 2) + 2*S(4, 3) = 7 + 3*6 = 25.
Boas-Buck recurrence for column m = 3, and n = 5: S(5, 3) = (3/2)*((5/2)*S(4, 3) + 10*Bernoulli(2)*S(3, 3)) = (3/2)*(15 + 10*(1/6)*1) = 25. (End)
		

References

• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 835.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 310.
• J. H. Conway and R. K. Guy, The Book of Numbers, Springer, p. 92.
• F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 244.
• J. Riordan, An Introduction to Combinatorial Analysis, p. 48.

Links

• David W. Wilson, Table of n, a(n) for n = 0..10010
• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
• V. E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015.
• Peter Bala, The white diamond product of power series
• Paul Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Toda Chain Equations, Journal of Integer Sequences, 17 (2014), #14.2.3.
• Paul Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.
• Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
• Xi Chen, Bishal Deb, Alexander Dyachenko, Tomack Gilmore, and Alan D. Sokal, Coefficientwise total positivity of some matrices defined by linear recurrences, arXiv:2012.03629 [math.CO], 2020.
• R. M. Dickau, Stirling numbers of the second kind
• Gerard Duchamp, Karol A. Penson, Allan I. Solomon, Andrej Horzela, and Pawel Blasiak, One-parameter groups and combinatorial physics, arXiv:quant-ph/0401126, 2004.
• FindStat - Combinatorial Statistic Finder, The number of blocks in the set partition.
• Bill Gosper, Colored illustrations of triangle of Stirling numbers of second kind read mod 2, 3, 4, 5, 6, 7
• W. Steven Gray and Makhin Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 March 2013, Digital Object Identifier: 10.1109/SSST.2013.6524939.
• Aoife Hennessy and Paul Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials, J. Int. Seq. 14 (2011) # 11.8.2.
• Paweł Hitczenko, A class of polynomial recurrences resulting in (n/log n, n/log^2 n)-asymptotic normality, arXiv:2403.03422 [math.CO], 2024. See pp. 8-9.
• Mathias Pétréolle and Alan D. Sokal, Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions, arXiv:1907.02645 [math.CO], 2019.
• Claus Michael Ringel, The Catalan combinatorics of the hereditary artin algebras, arXiv preprint arXiv:1502.06553 [math.RT], 2015.
• X.-T. Su, D.-Y. Yang, and W.-W. Zhang, A note on the generalized factorial, Australasian Journal of Combinatorics, Volume 56 (2013), Pages 133-137.

Crossrefs

See especially A008277 which is the main entry for this triangle.

Cf. A008275, A039810-A039813, A048994.

A000110(n) = sum(S(n, k)) k=0..n, n >= 0. Cf. A085693.

Cf. A084938, A106800 (mirror image), A138378, A213061 (mod 2).

Cf. A059297, A354794.

Programs

Haskell

a048993 n k = a048993_tabl !! n !! k
a048993_row n = a048993_tabl !! n
a048993_tabl = iterate (\row ->
   [0] ++ (zipWith (+) row $ zipWith (*) [1..] $ tail row) ++ [1]) [1]
-- Reinhard Zumkeller, Mar 26 2012

Maple

for n from 0 to 10 do seq(Stirling2(n,k),k=0..n) od; # yields sequence in triangular form # Emeric Deutsch, Nov 01 2006

Mathematica

t[n_, k_] := StirlingS2[n, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Robert G. Wilson v *)

Maxima

create_list(stirling2(n,k),n,0,12,k,0,n); /* Emanuele Munarini, Mar 11 2011 */

PARI

for(n=0, 22, for(k=0, n, print1(stirling(n, k, 2), ", ")); print()); \\ Joerg Arndt, Apr 21 2013

Formula

S(n, k) = k*S(n-1, k) + S(n-1, k-1), n > 0; S(0, k) = 0, k > 0; S(0, 0) = 1.

Equals [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is Deléham's operator defined in A084938.

Sum_{k = 0..n} x^k*S(n, k) = A213170(n), A000587(n), A000007(n), A000110(n), A001861(n), A027710(n), A078944(n), A144180(n), A144223(n), A144263(n) respectively for x = -2, -1, 0, 1, 2, 3, 4, 5, 6, 7. - Philippe Deléham, May 09 2004, Feb 16 2013

S(n, k) = Sum_{i=0..k} (-1)^(k+i)binomial(k, i)i^n/k!. - Paul Barry, Aug 05 2004

Sum_{k=0..n} k*S(n,k) = B(n+1)-B(n), where B(q) are the Bell numbers (A000110). - Emeric Deutsch, Nov 01 2006

Equals the inverse binomial transform of A008277. - Gary W. Adamson, Jan 29 2008

G.f.: 1/(1-xy/(1-x/(1-xy/(1-2x/(1-xy/1-3x/(1-xy/(1-4x/(1-xy/(1-5x/(1-... (continued fraction equivalent to Deléham DELTA construction). - Paul Barry, Dec 06 2009

G.f.: 1/Q(0), where Q(k) = 1 - (y+k)*x - (k+1)*y*x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013

Inverse of padded A008275 (padded just as A048993 = padded A008277). - Tom Copeland, Apr 25 2014

E.g.f. for the row polynomials s(n,x) = Sum_{k=0..n} S(n,k)*x^k is exp(x*(exp(z)-1)) (Sheffer property). E.g.f. for the k-th column sequence with k leading zeros is ((exp(x)-1)^k)/k! (Sheffer property). - Wolfdieter Lang, Oct 16 2014

G.f. for column k: x^k/Product_{j=1..k} (1-j*x), k >= 0 (with the empty product for k = 0 put to 1). See Abramowitz-Stegun, p. 824, 24.1.4 B. - Wolfdieter Lang, May 26 2017

Boas-Buck recurrence for column sequence m: S(n, k) = (k/(n - k))*(n*S(n-1, k)/2 + Sum_{p=k..n-2} (-1)^(n-p)*binomial(n,p)*Bernoulli(n-p)*S(p, k)), for n > k >= 0, with input T(k,k) = 1. See a comment and references in A282629. An example is given below. - Wolfdieter Lang, Aug 11 2017

The n-th row polynomial has the form x o x o ... o x (n factors), where o denotes the white diamond multiplication operator defined in Bala - see Example E4. - Peter Bala, Jan 07 2018

Sum_{k=1..n} k*S(n,k) = A138378(n). - Alois P. Heinz, Jan 07 2022

S(n,k) = Sum_{j=k..n} (-1)^(j-k)*A059297(n,j)*A354794(j,k). - Mélika Tebni, Jan 27 2023