|
| |
|
|
A008277
|
|
Triangle of Stirling numbers of the second kind, S2(n,k), n >= 1, 1 <= k <= n.
|
|
621
|
|
|
|
1, 1, 1, 1, 3, 1, 1, 7, 6, 1, 1, 15, 25, 10, 1, 1, 31, 90, 65, 15, 1, 1, 63, 301, 350, 140, 21, 1, 1, 127, 966, 1701, 1050, 266, 28, 1, 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1, 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1, 1, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
Also known as Stirling set numbers and written {n, k}.
S2(n,k) counts partitions of an n-set into k nonempty subsets.
Triangle S2(n,k), 1 <= k <= n, read by rows, given by [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is Deléham's operator defined in A084938.
Number of partitions of {1, ..., n+1} into k+1 nonempty subsets of nonconsecutive integers, including the partition 1|2|...|n+1 if n=k. E.g., S2(3,2)=3 since the number of partitions of {1,2,3,4} into three subsets of nonconsecutive integers is 3, i.e., 13|2|4, 14|2|3, 1|24|3. - Augustine O. Munagi, Mar 20 2005
Draw n cards (with replacement) from a deck of k cards. Let prob(n,k) be the probability that each card was drawn at least once. Then prob(n,k) = S2(n,k)*k!/k^n (see A090582). - Rainer Rosenthal, Oct 22 2005
Define f_1(x), f_2(x), ..., such that f_1(x)=e^x and for n = 2, 3, ..., f_{n+1}(x) = (d/dx)(x*f_n(x)). Then f_n(x) = e^x*Sum_{k=1..n} S2(n,k)*x^(k-1). - Milan Janjic, May 30 2008
For tables of restricted Stirling numbers of the second kind see A143494 - A143496.
S2(n,k) gives the number of 'patterns' of words of length n using k distinct symbols - see [Cooper & Kennedy] for an exact definition of the term 'pattern'. As an example, the words AADCBB and XXEGTT, both of length 6, have the same pattern of letters. The five patterns of words of length 3 are AAA, AAB, ABA, BAA and ABC giving row 3 of this table as (1,3,1).
Equivalently, S2(n,k) gives the number of sequences of positive integers (N_1,...,N_n) of length n, with k distinct entries, such that N_1 = 1 and N_(i+1) <= 1 + max{j = 1..i} N_j for i >= 1 (restricted growth functions). For example, Stirling(4,2) = 7 since the sequences of length 4 having 2 distinct entries that satisfy the conditions are (1,1,1,2), (1,1,2,1), (1,2,1,1), (1,1,2,2), (1,2,2,2), (1,2,2,1) and (1,2,1,2).
(End)
Number of combinations of subsets in the plane. - Mats Granvik, Jan 13 2009
S2(n+1,k+1) is the number of size k collections of pairwise disjoint, nonempty subsets of [n]. For example: S2(4,3)=6 because there are six such collections of subsets of [3] that have cardinality two: {(1)(23)},{(12)(3)}, {(13)(2)}, {(1)(2)}, {(1)(3)}, {(2)(3)}. - Geoffrey Critzer, Apr 06 2009
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1, k+1) equals the number of ways to choose 0 or more balls of each color in such a way that exactly (n-k) colors are chosen at least once, and no two colors are chosen the same positive number of times. - Matthew Vandermast, Nov 22 2010
S2(n,k) is the number of monotonic-labeled forests on n vertices with exactly k rooted trees, each of height one or less. See link "Counting forests with Stirling and Bell numbers" below. - Dennis P. Walsh, Nov 16 2011
If D is the operator d/dx, and E the operator xd/dx, Stirling numbers are given by: E^n = Sum_{k=1..n} S2(n,k) * x^k*D^k. - Hyunwoo Jang, Dec 13 2011
The Stirling polynomials of the second kind (a.k.a. the Bell / Touchard polynomials) are the umbral compositional inverses of the falling factorials (a.k.a. the Pochhammer symbol or Stirling polynomials of the first kind), i.e., binomial(Bell(.,x),n) = x^n/n! (cf. Copeland's 2007 formulas), implying binomial(xD,n) = binomial(Bell(.,:xD:),n) = :xD:^n/n! where D = d/dx and :xD:^n = x^n*D^n. - Tom Copeland, Apr 17 2014
S2(n,k) is the number of ways to nest n matryoshkas (Russian nesting dolls) so that exactly k matryoshkas are not contained in any other matryoshka. - Carlo Sanna, Oct 17 2015
The row polynomials R(n, x) = Sum_{k=1..n} S2(n, k)*x^k appear in the numerator of the e.g.f. of n-th powers, E(n, x) = Sum_{m>=0} m^n*x^m/m!, as E(n, x) = exp(x)*x*R(n, x), for n >= 1. - Wolfdieter Lang, Apr 02 2017
With offsets 0 for n and k this is the Sheffer product matrix A007318*A048993 denoted by (exp(t), (exp(t) - 1)) with e.g.f. exp(t)*exp(x*(exp(t) - 1)). - Wolfdieter Lang, Jun 20 2017
Number of words on k+1 unlabeled letters of length n+1 with no repeated letters. - Thomas Anton, Mar 14 2019
Also coefficients of moments of Poisson distribution about the origin expressed as polynomials in lambda. [Haight] (see also A331155). - N. J. A. Sloane, Jan 14 2020
k!*S2(n,k) is the number of surjections from an n-element set to a k-element set. - Jianing Song, Jun 01 2022
|
|
|
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.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 103ff.
B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
G. Boole, Finite Differences, 5th ed. New York, NY: Chelsea, 1970.
C. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, 2002, Theorem 8.11, pp. 298-299.
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.
S.N. Elaydi, An Introduction to Difference Equations, 3rd ed. Springer, 2005.
H. H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.7.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 244.
Frank Avery Haight, Handbook of the Poisson distribution, John Wiley, 1967. See pages 6,7.
A. D. Korshunov, Asymptotic behavior of Stirling numbers of the second kind. (Russian) Metody Diskret. Analiz. No. 39 (1983), 24-41.
E. Kuz'min and A. I. Shirshov: On the number e, pp. 111-119, eq.(6), in: Kvant Selecta: Algebra and Analysis, I, ed. S. Tabachnikov, Am.Math.Soc., 1999, p. 116, eq. (11).
J. Riordan, An Introduction to Combinatorial Analysis, p. 48.
J. Stirling, The Differential Method, London, 1749; see p. 7.
|
|
|
LINKS
|
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].
T. Copeland's Shadows of Simplicity, A Class of Differential Operators and the Stirling Numbers,2015; Generators, Inversion, and Matrix, Binomial, and Integral Transforms, 2015; The Inverse Mellin Transform, Bell Polynomials, a Generalized Dobinski Relation, and the Confluent Hypergeometric Functions, 2011; Mathemagical Forests, 2008; and Addendum to "Mathemagical Forests", 2010.
|
|
|
FORMULA
|
S2(n, k) = k*S2(n-1, k) + S2(n-1, k-1), n > 1. S2(1, k) = 0, k > 1. S2(1, 1) = 1.
E.g.f.: A(x, y) = e^(y*e^x-y). E.g.f. for m-th column: (e^x-1)^m/m!.
S2(n, k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i)*binomial(k, i)*i^n.
Row sums: Bell number A000110(n) = Sum_{k=1..n} S2(n, k), n>0.
S(n, k) = Sum (i_1*i_2*...*i_(n-k)) summed over all (n-k)-combinations {i_1, i_2, ..., i_k} with repetitions of the numbers {1, 2, ..., k}. Also S(n, k) = Sum (1^(r_1)*2^(r_2)*...* k^(r_k)) summed over integers r_j >= 0, for j=1..k, with Sum{j=1..k} r_j = n-k. [Charalambides]. - Wolfdieter Lang, Aug 15 2019.
For asymptotics see Hsu (1948), among other sources.
Sum_{n>=0} S2(n, k)*x^n = x^k/((1-x)(1-2x)(1-3x)...(1-kx)).
Let P(n) = the number of integer partitions of n (A000041), p(i) = the number of parts of the i-th partition of n, d(i) = the number of distinct parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, and Sum_{i=1..P(n), p(i)=m} = sum running from i=1 to i=P(n) but taking only partitions with p(i)=m parts into account. Then S2(n, m) = Sum_{i=1..P(n), p(i)=m} n!/(Product_{j=1..p(i)} p(i, j)!) * 1/(Product_{j=1..d(i)} m(i, j)!). For example, S2(6, 3) = 90 because n=6 has the following partitions with m=3 parts: (114), (123), (222). Their complexions are: (114): 6!/(1!*1!*4!) * 1/(2!*1!) = 15, (123): 6!/(1!*2!*3!) * 1/(1!*1!*1!) = 60, (222): 6!/(2!*2!*2!) * 1/(3!) = 15. The sum of the complexions is 15+60+15 = 90 = S2(6, 3). - Thomas Wieder, Jun 02 2005
Sum_{k=1..n} k*S2(n,k) = B(n+1)-B(n), where B(q) are the Bell numbers (A000110). - Emeric Deutsch, Nov 01 2006
Recurrence: S2(n+1,k) = Sum_{i=0..n} binomial(n,i)*S2(i,k-1). With the starting conditions S2(n,k) = 1 for n = 0 or k = 1 and S2(n,k) = 0 for k = 0 we have the closely related recurrence S2(n,k) = Sum_{i=k..n} binomial(n-1,i-1)*S2(i-1,k-1). - Thomas Wieder, Jan 27 2007
Representation of Stirling numbers of the second kind S2(n,k), n=1,2,..., k=1,2,...,n, as special values of hypergeometric function of type (n)F(n-1): S2(n,k)= (-1)^(k-1)*hypergeom([ -k+1,2,2,...,2],[1,1,...,1],1)/(k-1)!, i.e., having n parameters in the numerator: one equal to -k+1 and n-1 parameters all equal to 2; and having n-1 parameters in the denominator all equal to 1 and the value of the argument equal to 1. Example: S2(6,k)= seq(evalf((-1)^(k-1)*hypergeom([ -k+1,2,2,2,2,2],[1,1,1,1,1],1)/(k-1)!),k=1..6)=1,31,90,65,15,1. - Karol A. Penson, Mar 28 2007
Bell_n(x) = Sum_{j=0..n} S2(n,j) * x^j = Sum_{j=0..n} E(n,j) * Lag(n,-x, j-n) = Sum_{j=0..n} (E(n,j)/n!) * (n!*Lag(n,-x, j-n)) = Sum_{j=0..n} E(n,j) * binomial(Bell.(x)+j, n) umbrally where Bell_n(x) are the Bell / Touchard / exponential polynomials; S2(n,j), the Stirling numbers of the second kind; E(n,j), the Eulerian numbers; and Lag(n,x,m), the associated Laguerre polynomials of order m.
For x = 0, the equation gives Sum_{j=0..n} E(n,j) * binomial(j,n) = 1 for n=0 and 0 for all other n. By substituting the umbral compositional inverse of the Bell polynomials, the lower factorial n!*binomial(y,n), for x in the equation, the Worpitzky identity is obtained; y^n = Sum_{j=0..n} E(n,j) * binomial(y+j,n).
Note that E(n,j)/n! = E(n,j)/(Sum_{k=0..n}E(n,k)). Also (n!*Lag(n, -1, j-n)) is A086885 with a simple combinatorial interpretation in terms of seating arrangements, giving a combinatorial interpretation to the equation for x=1; n!*Bell_n(1) = n!*Sum_{j=0..n} S2(n,j) = Sum_{j=0..n} E(n,j) * (n!*Lag(n, -1, j-n)).
(Appended Sep 16 2020) For connections to the Bernoulli numbers, extensions, proofs, and a clear presentation of the number arrays involved in the identities above, see my post Reciprocity and Umbral Witchcraft. (End)
n-th row = leftmost column of nonzero terms of A127701^(n-1). Also, (n+1)-th row of the triangle = A127701 * n-th row; deleting the zeros. Example: A127701 * [1, 3, 1, 0, 0, 0, ...] = [1, 7, 6, 1, 0, 0, 0, ...]. - Gary W. Adamson, Nov 21 2007
The row polynomials are given by D^n(e^(x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A147315 and A094198. See also A185422. - Peter Bala, Nov 25 2011
O.g.f. for the n-th diagonal is D^n(x), where D is the operator x/(1-x)*d/dx. - Peter Bala, Jul 02 2012
n*i!*S2(n-1,i) = Sum_{j=(i+1)..n} (-1)^(j-i+1)*j!/(j-i)*S2(n,j). - Leonid Bedratyuk, Aug 19 2012
G.f.: (1/Q(0)-1)/(x*y), where Q(k) = 1 - (y+k)*x - (k+1)*y*x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result as A007318(x) = P(x).
With Bell(n,x)=B(n,x) defined above, D = d/dx, and :xD:^n = x^n*D^n, a Dobinski formula gives umbrally f(y)^B(.,x) = e^(-x)*e^(f(y)*x). Then f(y)^B(.,:xD:)g(x) = [f(y)^(xD)]g(x) = e^[-(1-f(y)):xD:]g(x) = g[f(y)x].
In particular, for f(y) = (1+y),
A) (1+y)^B(.,x) = e^(-x)*e^((1+y)*x) = e^(x*y) = e^[log(1+y)B(.,x)],
B) (I+dP)^B(.,x) = e^(x*dP) = P(x) = e^[x*(e^M-I)]= e^[M*B(.,x)] with dP = A132440, M = A238385-I = log(I+dP), and I = identity matrix, and
C) (1+dP)^(xD) = e^(dP:xD:) = P(:xD:) = e^[(e^M-I):xD:] = e^[M*xD] with action e^(dP:xD:)g(x) = g[(I+dP)*x].
D) P(x)^m = P(m*x), which implies (Sum_{k=1..m} a_k)^j = B(j,m*x) where the sum is umbrally evaluated only after exponentiation with (a_k)^q = B(.,x)^q = B(q,x). E.g., (a1+a2+a3)^2=a1^2+a2^2+a3^2+2(a1*a2+a1*a3+a2*a3) = 3*B(2,x)+6*B(1,x)^2 = 9x^2+3x = B(2,3x).
E) P(x)^2 = P(2x) = e^[M*B(.,2x)] = A038207(x), the face vectors of the n-Dim hypercubes.
(End)
As a matrix equivalent of some inversions mentioned above, A008277*A008275 = I, the identity matrix, regarded as lower triangular matrices. - Tom Copeland, Apr 26 2014
O.g.f. for the n-th diagonal of the triangle (n = 0,1,2,...): Sum_{k>=0} k^(k+n)*(x*e^(-x))^k/k!. Cf. the generating functions of the diagonals of A039755. Also cf. A112492. - Peter Bala, Jun 22 2014
Floor(1/(-1 + Sum_{n>=k} 1/S2(n,k))) = A034856(k-1), for k>=2. The fractional portion goes to zero at large k. - Richard R. Forberg, Jan 17 2015
Let x_(n), called a factorial term (Boole, 1970) or a factorial polynomial (Elaydi, 2005: p. 60), denote the falling factorial Product_{k=0..n-1} (x-k). Then, for n >= 1, x_(n) = Sum_{k=1..n} A008275(n,k) * x^k, x^n = Sum_{k=1..n} T(n,k) * x_(k), where A008275(n,k) are Stirling numbers of the first kind.
For n >= 1, the row sums yield the exponential numbers (or Bell numbers): Sum_{k=1..n} T(n,k) = A000110(n), and Sum_{k=1..n} (-1)^(n+k) * T(n,k) = (-1)^n * Sum_{k=1..n} (-1)^k * T(n,k) = (-1)^n * A000587(n), where A000587 are the complementary Bell numbers. (End)
O.g.f. for the m-th column: x^m/(Product_{j=1..m} 1-j*x). - Daniel Checa, Aug 25 2022
S2(n,k) ~ (k^n)/k!, for fixed k as n->oo. - Daniel Checa, Nov 08 2022
|
|
|
EXAMPLE
|
The triangle S2(n, k) begins:
\ k 1 2 3 4 5 6 7 8 9
n \ 10 11 12 13 14 15 ...
----------------------------------------------------------------------------------
1 | 1
2 | 1 1
3 | 1 3 1
4 | 1 7 6 1
5 | 1 15 25 10 1
6 | 1 31 90 65 15 1
7 | 1 63 301 350 140 21 1
8 | 1 127 966 1701 1050 266 28 1
9 | 1 255 3025 7770 6951 2646 462 36 1
10 | 1 511 9330 34105 42525 22827 5880 750 45
1
11 | 1 1023 28501 145750 246730 179487 63987 11880 1155
55 1
12 | 1 2047 86526 611501 1379400 1323652 627396 159027 22275
1705 66 1
13 | 1 4095 261625 2532530 7508501 9321312 5715424 1899612 359502
39325 2431 78 1
14 | 1 8191 788970 10391745 40075035 63436373 49329280 20912320 5135130
752752 66066 3367 91 1
15 | 1 16383 2375101 42355950 210766920 420693273 408741333 216627840 67128490
12662650 1479478 106470 4550 105 1
...
----------------------------------------------------------------------------------
x^4 = 1 x_(1) + 7 x_(2) + 6 x_(3) + 1 x_(4), where x_(k) = P(x,k) = k!*C(x,k). - Daniel Forgues, Jan 16 2016
|
|
|
MAPLE
|
seq(seq(combinat[stirling2](n, k), k=1..n), n=1..10); # Zerinvary Lajos, Jun 02 2007
stirling_2 := (n, k) -> (1/k!) * add((-1)^(k-i)*binomial(k, i)*i^n, i=0..k);
|
|
|
MATHEMATICA
|
BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
B = BellMatrix[1&, rows];
|
|
|
PROG
|
(PARI) for(n=1, 22, for(k=1, n, print1(stirling(n, k, 2), ", ")); print()); \\ Joerg Arndt, Apr 21 2013
(PARI) Stirling2(n, k)=sum(i=0, k, (-1)^i*binomial(k, i)*i^n)*(-1)^k/k! \\ M. F. Hasler, Mar 06 2012
(Haskell)
a008277 n k = a008277_tabl !! (n-1) !! (k-1)
a008277_row n = a008277_tabl !! (n-1)
(Maxima) create_list(stirling2(n+1, k+1), n, 0, 30, k, 0, n); /* Emanuele Munarini, Jun 01 2012 */
(J) n ((] (1 % !)) * +/@((^~ * (] (_1 ^ |.)) * (! {:)@]) i.@>:)) k NB. Stephen Makdisi, Apr 06 2016
(Magma) [[StirlingSecond(n, k): k in [1..n]]: n in [1..12]]; // G. C. Greubel, May 22 2019
|
|
|
CROSSREFS
|
Cf. A008275 (Stirling numbers of first kind), A048993 (another version of this triangle).
Cf. A000217, A001296, A001297, A001298, A007318, A028246, A039810-A039813, A048994, A087107-A087111, A087127, A094262, A127701.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
