1,5

Also known as Stirling set numbers and written {n, k}. S2(n,k) enumerates partitions of an n-set into k non-empty 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 Deleham's operator defined in A084938.

Number of partitions of {1, ...,n+1} into k+1 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. - A. O. Munagi (amunagi(AT)yahoo.com), 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 (r.rosenthal(AT)web.de), Oct 22 2005

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.

Moussa Benoumhani, The Number of Topologies on a Finite Set, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.

Bleick, W. E. and Wang, Peter C. C., Asymptotics of Stirling numbers of the second kind. Proc. Amer. Math. Soc. 42 (1974), 575-580.

Bleick, W. E. and Wang, Peter C. C., Erratum to: "Asymptotics of Stirling numbers of the second kind" (Proc. Amer. Math. Soc. {42} (1974), 575-580). Proc. Amer. Math. Soc. 48 (1975), 518.

B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 42.

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.

Ghislain R. Franssens, On a Number Pyramid Related to the Binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.

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.

Yoshinari Inaba, Hyper-Sums of Powers of Integers and the Akiyama-Tanigawa Matrix, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.7.

Knessl, Charles and Keller, Joseph B., Stirling number asymptotics from recursion equations using the ray method. Stud. Appl. Math. 84 (1991), no. 1, 43-56.

Korshunov, A. D., Asymptotic behavior of Stirling numbers of the second kind. (Russian) Metody Diskret. Analiz. No. 39 (1983), 24-41.

Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

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

N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.

A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, International Journal of Mathematics and Mathematical Sciences, 2005:2, (2005), 215-224.

J. Riordan, An Introduction to Combinatorial Analysis, p. 48.

J. Stirling, The Differential Method, London, 1749; see p. 7.

Temme, N. M. Asymptotic estimates of Stirling numbers. Stud. Appl. Math. 89 (1993), no. 3, 233-243.

Timashev, A. N. On asymptotic expansions of Stirling numbers of the first and second kinds. (Russian) Diskret. Mat. 10 (1998), no. 3,148-159 translation in Discrete Math. Appl. 8 (1998), no. 5, 533-544.

M. C. Wolf, Symmetric functions for non-commutative elements, Duke Math. J., 2 (1936), 626-637.

T. D. Noe, First 100 rows, flattened

Joerg Arndt, Fxtbook

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, December 1972 [alternative scanned copy].

P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers

P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem.

R. M. Dickau, Stirling numbers of the second kind

G. Duchamp, K. A. Penson, A. I. Solomon, A. Horzela and P. Blasiak, One-parameter groups and combinatorial physics.

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, International Journal of Mathematics and Mathematical Sciences, 2005:2 (2005), 215-224.

K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem

S. Ramanujan, Notebook entry

A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, Partition functions and graphs: A combinatorial approach.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Stirling numbers of the 2nd kind.

Eric Weisstein's World of Mathematics, Differential Operator

Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).

Thomas Wieder, Home Page.

Thomas Wieder, (Old) Home Page.

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, pp. 17ff, 105ff.

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)=exp(y*exp(x)-y). E.g.f. for m-th column: ((exp(x)-1)^m)/m!.

S2(n, k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i)*C(k, i)*i^n.

Bell number A000110(n) = sum(S(n, k)) k=1..n, n>0.

The k-th row (k>=1) contains a(n, k) for n=1 to k where a(n, k) = (1/(n-1)!) * Sum_{q=1..[2*n+1+(-1)^(n-1)]/4} [ C(n-1, 2*q-2)*(n-2*q+2)^(k-1) -C(n-1, 2*q-1)*(n-2*q+1)^(k-1) ]. E.g. Row 7 contains S2(7, 3)=301 { A001298, S2(n+4, n) } and will be computed as the following: S2(7, 3) = a(3, 7) = 1/(3-1)! * Sum_{q=1..2} [ C(3-1, 2*q-2)*(3-2*q+2)^(7-1) -C(3-1, 2*q-1)*(3-2*q+1)^(7-1) ] = Sum_{q=1..2} [ C(2, 2*q-2)*(5-2*q)^6 -C(2, 2*q-1)*(4-2*q)^6 ]/2! = [ C(2, 0)*3^6 -C(2, 1)*2^6 +C(2, 2)*1^6 -C(2, 3)*0^6 ]/2! = [ 729 -128 +1 -0 ]/2 = 301. - Andre F. Labossiere (boronali(AT)laposte.net), Jun 07 2004

For k>0 and for all x sufficiently small, Sum[n>=0, T(n, k)*x^n ] = x^k/[(1-x)(1-2x)(1-3x)...(1-kx)].

With P(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different 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, sum_[p(i)=m]_{i=1}^{P(n)} = sum running from i=1 to i=p(n) but taking only partitions with p(i)=m parts into account, prod_{j=1}^{p(i)} = product running from j=1 to j=p(i), prod_{j=1}^{d(i)} = product running from j=1 to j=d(i) one has S2(n, m) = sum_[p(i)=m]_{i=1}^{P(n)} (n!/prod_{j=1}^{p(i)} p(i, j)!) (1/prod_{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 (wieder.thomas(AT)t-online.de), Jun 02 2005

Sum(k*S2(n,k), k=1..n)=B(n+1)-B(n), where B(q) are the Bell numbers (A000110). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 01 2006

Recurrence: S2(n+1,k) = sum_{i=0}^n C(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 C(n-1,i-1) S2(i-1, k-1) where C(n,m) is the binomial coefficient. - Thomas Wieder (thomas.wieder(AT)t-online.de), Jan 27 2007

Formulae and comments from Tom Copeland, Oct 10 2007 (Start): 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) * C(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; Lag(n,x,m), the associated Laguerre polynomials of order m; and C(x,y) = x!/[ y!*(x-y)! ].

By substituting the umbral compositional inverse of the Bell polynomials, the lower factorial n!*C(x,n), for x in the equation, the equation becomes x^n = sum(j=0,...,n) S2(n,j) * j! * C(x,j)

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)]} . (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 (qntmpkt(AT)yahoo.com), Nov 21 2007

Triangle begins:

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

stirling_2 := (n, k) -> (1/k!) * add((-1)^(k-i)*binomial(k, i)*i^n, i=0..k);

Stirling2rec := proc(n::integer, k::integer) # Calculate the Stirling numbers of the second kind S2(n, k) by a recurrence. local i, Result; if k > n or n < 0 or k < 0 then return fail end if; if n = 0 or k = 1 then Result := 1; return Result end if; if k = 0 then Result := 0; return Result end if; Result := 0; for i from k to n do Result := Result + binomial(n - 1, i - 1) * Stirling2rec(i - 1, k - 1); end do; return Result; end proc; - Thomas Wieder (thomas.wieder(AT)t-online.de), 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). In Maple notation: stirling2(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: stirling2(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 ( penson(AT)lptl.jussieu.fr ), Mar 28 2007

with (combinat):seq(seq(stirling2(n, k), k=1..n), n=1..10); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 02 2007

for i from 0 to 10 do seq(stirling2(i, j), j = 1 .. i) od; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Nov 29 2007

Table[StirlingS2[n, k], {n, 11}, {k, n}] // Flatten (from Robert G. Wilson v (rgwv(at)rgwv.com), May 23 2006)

(PARI) S2(n, k) = if(k<1|k>n, 0, if(n==1, 1, k*S2(n-1, k)+S2(n-1, k-1))); printp(matrix(9, 9, n, k, S2(n, k)))

Cf. A008275 (Stirling numbers of first kind), A039810-A039813, A048993 (another version of this triangle), A048994, A028246.

Cf. A028246, A094262, A000217, A001296, A001297, A001298, A087127, A087107-A087111.

Two closely related triangles are A19538(n,k)=k!* S2(n,k) and A028248(n,k) = (k-1)!*S2(n,k).

Cf. A127701.

Adjacent sequences: A008274 A008275 A008276 this_sequence A008278 A008279 A008280

Sequence in context: A094507 A065625 A130749 this_sequence A080417 A133800 A132733

nonn,tabl,nice,core

njas