Talk:Stirling numbers of the second kind

Unclear

I'm removing a large block of text from this article, because it is unclear. The problems are:

• Use of blackpage symbols without any attempt to explain their meaning
• Use of the term "EGF" without explaining what it means. Is this, perhaps, the exponential generating function? or something else?
• Use of the symbol $[x^{n}]$ without explanation. Clearly, its not equal to $x^{n}$, but I can't figure out what its supposed to be. (edit: $[x^{n}]$ denotes the coefficient of $x^{n}$ in the power series expansion of the specified generating function)
• Most of the text appears to be a long proof, and, as such, is not appropriate for article space. See Category:Article proofs for examples on how to deal with proofs.

linas 02:16, 29 December 2006 (UTC)

Generating functions

These numbers count the number of partitions of $[n]$ into k nonempty subsets. First consider the total number of partitions, i.e. $B_{n}$ where

$B_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}{\mbox{ and }}B_{0}=1,$

i.e. the Bell numbers. The Symbolic combinatorics#The Flajolet–Sedgewick fundamental theorem applies (labelled case). The set ${\mathcal {B}}\,$ of partitions into non-empty subsets is given by ("set of non-empty sets of singletons")

${\mathcal {B}}={\mathfrak {P}}({\mathfrak {P}}_{\geq 1}({\mathcal {Z}})).$

This decomposition is entirely analogous to the construction of the set ${\mathcal {P}}\,$ of permutations from cycles, which is given by

${\mathcal {P}}={\mathfrak {P}}({\mathfrak {C}}({\mathcal {Z}})).$

and yields the Stirling numbers of the first kind. Hence the name "Stirling numbers of the second kind."

The decomposition is equivalent to the EGF

$B(z)=\exp \left(\exp z-1\right).$

Differentiate to obtain

${\frac {d}{dz}}B(z)=\exp \left(\exp z-1\right)\exp z=B(z)\exp z,$

which implies that

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k},$

by convolution of exponential generating functions and because differentiating an EGF drops the first coefficient and shifts $B_{n+1}$ to $z^{n}/n!.$

The EGF of the Stirling numbers of the second kind is obtained by marking every subset that goes into the partition with the term ${\mathcal {U}}\,$, giving

${\mathcal {B}}={\mathfrak {P}}({\mathcal {U}}\;{\mathfrak {P}}_{\geq 1}({\mathcal {Z}})).$

Translating to generating functions, we obtain

$B(z,u)=\exp \left(u\left(\exp z-1\right)\right).$

This EGF yields the formula for the Stirling numbers of the second kind:

$\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=n![u^{k}][z^{n}]B(z,u)=n![z^{n}]{\frac {(\exp z-1)^{k}}{k!}}$

or

$n![z^{n}]{\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}\exp(jz)(-1)^{k-j}$

which simplifies to

${\frac {n!}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}{\frac {j^{n}}{n!}}={\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}j^{n}.$

We can use $B(z,u)$ to evaluate the sum

$\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}(x)_{k}.$

This is equal to

$\sum _{k=0}^{n}n![u^{k}][z^{n}]B(z,u)(x)_{k}=n![z^{n}]\sum _{k=0}^{n}[u^{k}]B(z,u)(x)_{k}$

or

$n![z^{n}]\sum _{k=0}^{n}{\frac {(\exp z-1)^{k}}{k!}}(x)_{k}=n![z^{n}]\sum _{k=0}^{\infty }{\frac {(\exp z-1)^{k}}{k!}}(x)_{k}$

where the last equality occurs because $[z^{n}](\exp z-1)^{k}=0\,$ when $n<k\,.$

Now consider the Taylor series of $y^{x}$ at $y=1:$

$y^{x}=\sum _{k=0}^{\infty }\left(\left({\frac {d}{dy}}\right)^{k}y^{x}{\Bigg |}_{y=1}\right){\frac {(y-1)^{k}}{k!}}=\sum _{k=0}^{\infty }(x)_{k}{\frac {(y-1)^{k}}{k!}}.$

Hence

$\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}(x)_{k}=n![z^{n}]\exp(xz)=n!{\frac {x^{n}}{n!}}=x^{n}.$

Explicit formula

I have noticed that the index j in the sum of the explicit formula starts at 0 in all textbooks I have had a look on this topic. I understand that it does not matter, as the jⁿ part will make the whole thing zero anyway when j=0. Was just wondering if there is standard notation, since wikipedia is the first place where I have seen it starting at 1. —Preceding unsigned comment added by 130.95.29.113 (talk • contribs) 08:54, 25 May 2007 (UTC)

Its starts at j=0 to cover the case when n=0, because then we get $0^{0}=1$. --Ray andrew 21:48, 26 September 2007 (UTC)

n < k ?

I think the article could use a mention of whether or not n < k is allowed in

$\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$

Btyner (talk) 01:02, 21 January 2008 (UTC)

Combinatorial argument for explicit formula for S(n,k)

The article states that $S(n,k)$ is the number of k-partitions of an n-set and gives an explicit formula, but it is not clear how the explicit formula relates to partitions. Some exposition giving a combinatorial argument would be a welcome addition to the page. The $1/k!$ in the formula is clear since permuting the subsets in the partition does not give a different partition. The other factors in each term are less obvious to me. Steve Checkoway (talk) 00:52, 6 August 2008 (UTC)

There is a nice combinatorial argument for the recurrence (which I will add soon), but I've not seen one for the explicit formula. As is often the case in determining closed formulas, the solution lies in dry, analytic methods that rarely shed light on the underlying combinatorial structure. Austinmohr (talk) 07:44, 12 October 2008 (UTC)

It's an uncomplicated application of inclusion/exclusion. That proof is quite comprehensible. Zaslav (talk) 03:05, 15 November 2013 (UTC)

Cerial Box Problem?

This is either not well defined or just wrong. Since both, boxes and prices are distinguishable, the events (1,1,2,3) and (2,2,1,3) should be counted individually. So the number of cases when you get all three prizes after buying 4 boxes is $3!S(4,3)$, or in general $k!S(n,k)$. The problem is related to the Coupon collector's problem which asks how many boxes you need to collect all prizes (coupons), i.e. the stopping time for the renewal process $k(n)$ of having k different prizes after buying n boxes. —Preceding unsigned comment added by 133.65.54.177 (talk) 04:07, 3 March 2010 (UTC)

Right, I'll remove that section. Marc van Leeuwen (talk) 13:25, 12 September 2011 (UTC)

I dispute this as it doesn't matter which order you get the prizes – and they are often unordered, and because in fact cereal boxes in a given promotion are typically indistinguishable. Should the OP's complaint apply to the previous example, in which both lines of poetry and rhyming schemes are well-ordered? Regregex (talk) 14:20, 12 September 2011 (UTC)

No there is an essential difference between trinket collection and rhyming schemes. In a rhyming scheme, only the matching of rhymes is counted, not the actual rhymes. Thus, if you take a rhyme using an ABAB rhyming scheme, and you (for instance) reverse the lines, then you don't get a different BABA rhyming scheme, but again an ABAB scheme. However, in trinket collection the trinkets themselves are distinguished and collected; otherwise there can be no notion of getting all the trinkets (compare how strange it would be to require a scheme to involve all possible rhymes). If there are trinkets A,B,C, then finding A,B,A,C is different from finding B,C,B,A (one even has a different multi-set of trinkets at the end) even though in both cases one (only) finds identical trinkets in the first and third cerial box. The section is unhelpful and should go. Marc van Leeuwen (talk) 15:56, 12 September 2011 (UTC)

I intended to defend it's inclusion, but after looking at it more closely, I vote to remove the section. The Stirling numbers count the number of ways to arrange $n$ labeled balls into $k$ unlabeled buckets. This cereal box problem can either be interpreted as having labeled or unlabeled balls (i.e. cereal box openings) depending on whether you want to consider the order of the openings as important. In either scenario, however, the buckets (i.e. trinkets) are certainly labeled, and so the Stirling numbers are an inappropriate model. Austinmohr (talk) 19:31, 13 September 2011 (UTC)

I'll respect the consensus, but I maintain that a Monty Hall-style error has occurred. Consider the case where you only know the number of prizes in advance, not their names or appearances (their location in a packshot or gallery might impose an order). You can tell when your collection is complete, but not that the prize in the first box is trinket B. Regregex (talk) 14:25, 16 September 2011 (UTC)

Reduced variations

The source listed as [1] here does not seem to be a peer-reviewed or expertly edited document. Has major typographic error even on first page. This should probably be removed awaiting further documentation. —Preceding unsigned comment added by 65.209.156.130 (talk • contribs) 2010-04-28T16:30:20Z

There are two sources listed as [1], but to be clear the second one, the one in the section on "reduced" is pretty clearly self-published by the editor who inserted this section, in this edit. Similar concerns were raised at Talk:Distributive lattice#External links, so I removed the section as original research and conflict of interest. JackSchmidt (talk) 17:01, 28 April 2010 (UTC)

I am one of the authors of the paper in question. The article had not yet been published when I originally uploaded it (though it had already been reviewed), but now appears in the Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 70 (2009), pg. 57 - 64. I am presently reverting the edit, but am open to discussing the issue further. Austinmohr (talk) 05:14, 6 May 2010 (UTC)

I think that section in the article should be removed; it does not say much about the subject of this article. Marc van Leeuwen (talk) 13:27, 12 September 2011 (UTC)

It is a natural generalization of the topic at hand, so I do not think it is off-topic, nor is it a particularly lengthy addition to the article. Austinmohr (talk) 20:16, 12 September 2011 (UTC)

Generating function

The identity given in this section is not really the generating function in the usual sense ....

Summsumm (talk) 10:13, 17 September 2010 (UTC)

Typo in definition

The lead in the Definition section:

“ The Stirling numbers of the second kind S(n,k) count the number of ways to partition a set of n elements into k nonempty (and nondistinct) subsets. They can be calculated using the following explicit formula ”

I suppose, "nonempty" is correct, but "nondistinct" may have been originated as a typo. I suppose, it was originally meant as "nonempty and disjoint".

“ The Stirling numbers of the second kind S(n,k) count the number of ways to partition a set of n elements into k nonempty (and disjoint) subsets. They can be calculated using the following explicit formula ”

Physis (talk) 10:02, 8 January 2011 (UTC)

A partition of a set is a collection of disjoint subsets whose union is the original set. Thus, disjointness is very explicit in the definition of a partition. Slightly less explicit is the fact that the subsets are nondistinct. That is, there is no ordering placed on the subsets. For example, if the original set is {1, 2, 3}, the partition {{1},{2,3}} is considered to be the same as the partition {{2,3},{1}}. Perhaps it is less confusing to just remove the mention of distinctness altogether (since it is already a part of the definition of a partition). Austinmohr (talk) 04:21, 9 January 2011 (UTC)

"nondistinct" is not the right adjective; if anything it would mean "identical" which is wrong. It should say "unlabeled", which is the conventional term in combinatorics in such situations. A surjection to {1,2, ..., k} would define a partition of the original set, but with the parts labeled (by their common image). See also Twelvefold way for more of this. Marc van Leeuwen (talk) 07:40, 14 September 2011 (UTC)

Explicit formula for S(n,3) is wrong

The explicit formula for S(n,3) is incorrect. I don't know what causes the problem, but the formula is translated by 2 from the correct one. — Preceding unsigned comment added by 77.254.110.81 (talk) 03:37, 13 May 2013 (UTC)

Which formula? (There are several.) The ones I checked looked fine. --JBL (talk) 13:31, 13 May 2013 (UTC)

Pronunciation

Can someone comment on how you would read $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$ aloud? — Preceding unsigned comment added by Garfieldnate (talk • contribs) 14:22, 16 September 2014 (UTC)

Citation for exact formula

The citation for the exact formula in the Stirling_numbers_of_the_second_kind#Definitiondefinition section was to the following article:

• Sharp, Henry (1968), "Cardinality of finite topologies", J. Combinatorial Theory, 5: 82–86, doi:10.1016/S0021-9800(68)80031-6, MR 0226578

I deleted the citation because it does not support the claim at all. Sharp's paper doesn't contain the formula and, in fact, it doesn't even mention Stirling numbers. Since the paper is completely irrelevant to the article, I followed the advice on the Failed Verification template page and replaced the citation with "Citation needed" rather than "Failed Verification". Dricherby (talk) 12:01, 17 June 2016 (UTC)

Well-caught. Here's one possible reference: Richard Stanley, EC1, second edition, equation (1.94a) (page 82 of the online edition http://math.mit.edu/~rstan/ec/ec1.pdf ). --JBL (talk) 16:23, 17 June 2016 (UTC)

Asymptotics section

The uniform asymptotic formula is not correct as written. I have gone through the Temme reference (which is the only one that is needed there; the Bleick and Wang reference does not apply). The correct formula is

$\left\{{n \atop k}\right\}\sim {\sqrt {\frac {v-1}{v(1-G)}}}\left({\frac {v-1}{v-G}}\right)^{n-k}{\frac {k^{n}}{n^{k}}}e^{k(1-G)}\left({n \atop k}\right).$

I have also checked this in Mathematica when k is of the same order as n. 14.139.128.30 (talk) 12:43, 21 March 2019 (UTC)

Corrected a minor typo. 14.139.128.30 (talk) 04:45, 25 March 2019 (UTC)

Wording

"In mathematics, particularly in combinatorics, a Stirling number of the second kindis the number of ways [...]. [They] occur in the field of mathematics called combinatorics and the study of partitions."

This repeats both mathematics and combinatorics, and even links them in all cases. Is that really necessary?

2003:6:5318:A655:7709:61A7:8DDF:60E5 (talk) 18:44, 14 April 2020 (UTC)