Talk:Stirling numbers of the second kind

Latest comment: 4 years ago by 2003:6:5318:A655:7709:61A7:8DDF:60E5 in topic Wording

Unclear

edit

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   without explanation. Clearly, its not equal to  , but I can't figure out what its supposed to be. (edit:   denotes the coefficient of   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)Reply

Generating functions

edit

These numbers count the number of partitions of   into k nonempty subsets. First consider the total number of partitions, i.e.   where

 

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

 

This decomposition is entirely analogous to the construction of the set   of permutations from cycles, which is given by

 

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

 

Differentiate to obtain

 

which implies that

 

by convolution of exponential generating functions and because differentiating an EGF drops the first coefficient and shifts   to  

The EGF of the Stirling numbers of the second kind is obtained by marking every subset that goes into the partition with the term  , giving

 

Translating to generating functions, we obtain

 

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

 

or

 

which simplifies to

 

We can use   to evaluate the sum

 

This is equal to

 

or

 

where the last equality occurs because   when  

Now consider the Taylor series of   at  

 

Hence

 

Explicit formula

edit

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 jn 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 (talkcontribs) 08:54, 25 May 2007 (UTC)Reply

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

n < k ?

edit

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

 

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

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

edit

The article states that   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   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)Reply

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)Reply
It's an uncomplicated application of inclusion/exclusion. That proof is quite comprehensible. Zaslav (talk) 03:05, 15 November 2013 (UTC)Reply

Cerial Box Problem?

edit

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  , or in general  . 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   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)Reply

Right, I'll remove that section. Marc van Leeuwen (talk) 13:25, 12 September 2011 (UTC)Reply
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)Reply
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)Reply
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)Reply
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)Reply

Reduced variations

edit

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 (talkcontribs) 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)Reply
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)Reply
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)Reply
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)Reply

Generating function

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

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

Typo in definition

edit

The lead in the Definition section:



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



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

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)Reply
"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)Reply

Explicit formula for S(n,3) is wrong

edit

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

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

Pronunciation

edit

Can someone comment on how you would read   aloud? — Preceding unsigned comment added by Garfieldnate (talkcontribs) 14:22, 16 September 2014 (UTC)Reply

Citation for exact formula

edit

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

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

Asymptotics section

edit

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

 

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

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

Wording

edit

"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)Reply