%I A008277
%S A008277 1,1,1,1,3,1,1,7,6,1,1,15,25,10,1,1,31,90,65,15,1,1,63,301,
%T A008277 350,140,21,1,1,127,966,1701,1050,266,28,1,1,255,3025,7770,
%U A008277 6951,2646,462,36,1,1,511,9330,34105,42525,22827,5880,750,45,1
%N A008277 Triangle of Stirling numbers of 2nd kind, S2(n,k), n >= 1, 1<=k<=n.
%C A008277 Also known as Stirling set numbers and written {n, k}. S2(n,k) enumerates
partitions of an n-set into k non-empty subsets.
%C A008277 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.
%C A008277 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
%C A008277 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
%C A008277 Define f_1(x),f_2(x),... such that f_1(x)=e^x and for n=2,3,... f_{n+1}(x)=diff(x*f_n(x),
x). Then f_n(x)=e^x*sum(stirling2(n,k)*x^(k-1),k=1..n). - Milan R.
Janjic (agnus(AT)blic.net), May 30 2008
%C A008277 Contribution from Peter Bala (pbala(AT)toucansurf.com), Oct 03 2008:
(Start)
%C A008277 For tables of restricted Stirling numbers of the second kind see A143494
- A143496.
%C A008277 Stirling2(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).
%C A008277 Equivalently, Stirling2(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. 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)
%C A008277 The row sums give A000110: {1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975,
...} [From Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Jan 11 2009]
%C A008277 Number of combinations of subsets in the plane. [From Mats Granvik (mats.granvik(AT)abo.fi),
Jan 13 2009]
%C A008277 Contribution from Geoffrey Critzer (critzer.geoffrey(AT)usd443.org),
Apr 06 2009: (Start)
%C A008277 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)},
%C A008277 {(1)(2)},{(1)(3)},{(2)(3)} (End)
%D A008277 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.
%D A008277 A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of
combinatorial proof, M.A.A. 2003, p. 103ff.
%D A008277 Moussa Benoumhani, The Number of Topologies on a Finite Set, Journal
of Integer Sequences, Vol. 9 (2006), Article 06.2.6.
%D A008277 Bleick, W. E. and Wang, Peter C. C., Asymptotics of Stirling numbers
of the second kind. Proc. Amer. Math. Soc. 42 (1974), 575-580.
%D A008277 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.
%D A008277 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.
%D A008277 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 310.
%D A008277 J. H. Conway and R. K. Guy, The Book of Numbers, Springer, p. 92.
%D A008277 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied
Tables, Cambridge, 1966, p. 223.
%D A008277 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.
%D A008277 H. H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977;
Section 2.7.
%D A008277 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley,
Reading, MA, 1990, p. 244.
%D A008277 Yoshinari Inaba, Hyper-Sums of Powers of Integers and the Akiyama-Tanigawa
Matrix, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.7.
%D A008277 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.
%D A008277 Korshunov, A. D., Asymptotic behavior of Stirling numbers of the second
kind. (Russian) Metody Diskret. Analiz. No. 39 (1983), 24-41.
%D A008277 Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal
of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
%D A008277 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).
%D A008277 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.
%D A008277 A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, International
Journal of Mathematics and Mathematical Sciences, 2005:2, (2005),
215-224.
%D A008277 J. Riordan, An Introduction to Combinatorial Analysis, p. 48.
%D A008277 J. Stirling, The Differential Method, London, 1749; see p. 7.
%D A008277 Temme, N. M. Asymptotic estimates of Stirling numbers. Stud. Appl. Math.
89 (1993), no. 3, 233-243.
%D A008277 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.
%D A008277 M. C. Wolf, Symmetric functions for non-commutative elements, Duke Math.
J., 2 (1936), 626-637.
%H A008277 T. D. Noe, <a href="b008277.txt">First 100 rows, flattened</a>
%H A008277 K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp and A. I. Solomon,
<a href="http://arxiv.org/abs/0904.0369">Laguerre-type derivatives:
Dobinski relations and combinatorial identities</a>, J. Math. Phys.
vol. 50, 083512 (2009)
%H A008277 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A008277 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.nrbook.com/
abramowitz_and_stegun/">Handbook of Mathematical Functions</a>, National
Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972
[alternative scanned copy].
%H A008277 P. Blasiak, K. A. Penson and A. I. Solomon, <a href="http://arXiv.org/
abs/quant-ph/0212072">The Boson Normal Ordering Problem and Generalized
Bell Numbers</a>
%H A008277 P. Blasiak, K. A. Penson and A. I. Solomon, <a href="http://www.arXiv.org/
abs/quant-ph/0402027">The general boson normal ordering problem.</
a>
%H A008277 C. Cooper and R. E. Kennedy, <a href="http://www.math-cs.ucmo.edu/~curtisc/
articles.html">Patterns, automata and Stirling numbers of the second
kind</a>, Mathematics and Computer Education Journal, 26 (1992),
120-124. [From Peter Bala (pbala(AT)toucansurf.com), Oct 03 2008]
%H A008277 R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/stirling2.html">
Stirling numbers of the second kind</a>
%H A008277 G. Duchamp, K. A. Penson, A. I. Solomon, A. Horzela and P. Blasiak, <a
href="http://arXiv.org/abs/quant-ph/0401126">One-parameter groups
and combinatorial physics</a>.
%H A008277 A. F. Labossiere, <a href="http://members.lycos.co.uk/sobalian/index.html">
Sobalian Coefficients</a>.
%H A008277 A. F. Labossiere, <a href="http://members.lycos.co.uk/stereotomography/
index.html">Miscellaneous</a>.
%H A008277 W. Lang, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
On generalizations of Stirling number triangles</a>, J. Integer Seqs.,
Vol. 3 (2000), #00.2.4.
%H A008277 A. O. Munagi, <a href="http://www.hindawi.com/getarticle.aspx?doi=10.1155/
IJMMS.2005.215"> k- Complementing Subsets of Nonnegative Integers</
a>, International Journal of Mathematics and Mathematical Sciences,
2005:2 (2005), 215-224.
%H A008277 K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, <a
href="http://arXiv.org/abs/quant-ph/0312202">Hierarchical Dobinski-type
relations via substitution and the moment problem</a>
%H A008277 S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/NoteBooks/
NoteBook2/chapterIII/page4.htm">Notebook entry</a>
%H A008277 A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, <a
href="http://arXiv.org/abs/quant-ph/0409082">Partition functions
and graphs: A combinatorial approach</a>.
%H A008277 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
StirlingNumberoftheSecondKind.html">Link to a section of The World
of Mathematics.</a>
%H A008277 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
StirlingNumberoftheSecondKind.html">Stirling numbers of the 2nd kind</
a>.
%H A008277 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
DifferentialOperator.html">Differential Operator</a>
%H A008277 Thomas Wieder, The number of certain k-combinations of an n-set, <a href="http:/
/www.math.nthu.edu.tw/~amen/">Applied Mathematics Electronic Notes</
a>, vol. 8 (2008).
%H A008277 Thomas Wieder, <a href="http://www.thomas-wieder.privat.t-online.de/default.html">
Home Page</a>.
%H A008277 Thomas Wieder, <a href="http://homepages.tu-darmstadt.de/~wieder/Welcome.html">
(Old) Home Page</a>.
%H A008277 H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</
a>, 2nd edn., Academic Press, NY, 1994, pp. 17ff, 105ff.
%F A008277 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.
%F A008277 E.g.f.: A(x, y)=exp(y*exp(x)-y). E.g.f. for m-th column: ((exp(x)-1)^m)/
m!.
%F A008277 S2(n, k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i)*C(k, i)*i^n.
%F A008277 Bell number A000110(n) = sum(S(n, k)) k=1..n, n>0.
%F A008277 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
%F A008277 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)].
%F A008277 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
%F A008277 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
%F A008277 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
%F A008277 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)! ].
%F A008277 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)
%F A008277 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)
%F A008277 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
%F A008277 Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Jan 11
2009: (Start)
%F A008277 p(x,n)=Sum[m^n*x^m/m!, {m, 0, Infinity}]/(x*Exp[x]);
%F A008277 s(n,m)=coefficients(p(x,n)) (End)
%e A008277 Triangle begins:
%e A008277 {1},
%e A008277 {1, 1},
%e A008277 {1, 3, 1},
%e A008277 {1, 7, 6, 1},
%e A008277 {1, 15, 25, 10, 1},
%e A008277 {1, 31, 90, 65, 15, 1},
%e A008277 {1, 63, 301, 350, 140, 21, 1},
%e A008277 {1, 127, 966, 1701, 1050, 266, 28, 1},
%e A008277 {1, 255, 3025, 7770, 6951, 2646, 462, 36, 1},
%e A008277 {1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1}
%e A008277 ...
%p A008277 stirling_2 := (n,k) -> (1/k!) * add((-1)^(k-i)*binomial(k,i)*i^n, i=0..k);
%p A008277 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
%p A008277 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
%p A008277 with (combinat):seq(seq(stirling2(n, k), k=1..n), n=1..10); - Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Jun 02 2007
%p A008277 for i from 0 to 10 do seq(stirling2(i, j), j = 1 .. i) od; - Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Nov 29 2007
%t A008277 Table[StirlingS2[n, k], {n, 11}, {k, n}] // Flatten (from Robert G. Wilson
v (rgwv(at)rgwv.com), May 23 2006)
%t A008277 Contribution from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Jan 11
2009: (Start)
%t A008277 p[x_, n_] = Sum[m^n*x^m/m!, {m, 0, Infinity}]/(x*Exp[x]);
%t A008277 Table[FullSimplify[ExpandAll[p[x, n]]], {n, 1, 10}];
%t A008277 Table[CoefficientList[FullSimplify[ExpandAll[p[x, n]]], x], {n, 1, 10}];
%t A008277 Flatten[%] (End)
%o A008277 (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)))
%Y A008277 Cf. A008275 (Stirling numbers of first kind), A039810-A039813, A048993
(another version of this triangle), A048994, A028246.
%Y A008277 Cf. A028246, A094262, A000217, A001296, A001297, A001298, A087127, A087107-A087111.
%Y A008277 Two closely related triangles are A19538(n, k)=k!* S2(n, k) and A028248(n,
k) = (k-1)!*S2(n, k).
%Y A008277 Cf. A127701.
%Y A008277 Sequence in context: A154341 A130749 A154959 this_sequence A080417 A133800
A146900
%Y A008277 Adjacent sequences: A008274 A008275 A008276 this_sequence A008278 A008279
A008280
%K A008277 nonn,tabl,nice,core
%O A008277 1,5
%A A008277 N. J. A. Sloane (njas(AT)research.att.com).
|
