In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or .[1] Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.
The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the second kind. Identities linking the two kinds appear in the article on Stirling numbers.
Definition
The Stirling numbers of the second kind, written or or with other notations, count the number of ways to partition a set of labelled objects into nonempty unlabelled subsets. Equivalently, they count the number of different equivalence relations with precisely equivalence classes that can be defined on an element set. In fact, there is a bijection between the set of partitions and the set of equivalence relations on a given set. Obviously,
for n ≥ 0, and for n ≥ 1,
as the only way to partition an n-element set into n parts is to put each element of the set into its own part, and the only way to partition a nonempty set into one part is to put all of the elements in the same part. Unlike Stirling numbers of the first kind, they can be calculated using a one-sum formula:[2]
The Stirling numbers of the first kind may be characterized as the numbers that arise when one expresses powers of an indeterminate x in terms of the falling factorials[3]
(In particular, (x)0 = 1 because it is an empty product.)
Stirling numbers of the second kind satisfy the relation
Notation
Various notations have been used for Stirling numbers of the second kind. The brace notation was used by Imanuel Marx and Antonio Salmeri in 1962 for variants of these numbers.[4][5] This led Knuth to use it, as shown here, in the first volume of The Art of Computer Programming (1968).[6][7] According to the third edition of The Art of Computer Programming, this notation was also used earlier by Jovan Karamata in 1935.[8][9] The notation S(n, k) was used by Richard Stanley in his book Enumerative Combinatorics and also, much earlier, by many other writers.[6]
The notations used on this page for Stirling numbers are not universal, and may conflict with notations in other sources.
Below is a triangular array of values for the Stirling numbers of the second kind (sequence A008277 in the OEIS):
k
n
0
1
2
3
4
5
6
7
8
9
10
0
1
1
0
1
2
0
1
1
3
0
1
3
1
4
0
1
7
6
1
5
0
1
15
25
10
1
6
0
1
31
90
65
15
1
7
0
1
63
301
350
140
21
1
8
0
1
127
966
1701
1050
266
28
1
9
0
1
255
3025
7770
6951
2646
462
36
1
10
0
1
511
9330
34105
42525
22827
5880
750
45
1
As with the binomial coefficients, this table could be extended to k > n, but the entries would all be 0.
Properties
Recurrence relation
Stirling numbers of the second kind obey the recurrence relation
with initial conditions
For instance, the number 25 in column k = 3 and row n = 5 is given by 25 = 7 + (3×6), where 7 is the number above and to the left of 25, 6 is the number above 25 and 3 is the column containing the 6.
To prove this recurrence, observe that a partition of the objects into k nonempty subsets either contains the -th object as a singleton or it does not. The number of ways that the singleton is one of the subsets is given by
since we must partition the remaining n objects into the available subsets. In the other case the -th object belongs to a subset containing other objects. The number of ways is given by
since we partition all objects other than the -th into k subsets, and then we are left with k choices for inserting object . Summing these two values gives the desired result.
Another recurrence relation is given by
which follows from evaluating at .
Simple identities
Some simple identities include
This is because dividing n elements into n − 1 sets necessarily means dividing it into one set of size 2 and n − 2 sets of size 1. Therefore we need only pick those two elements;
and
To see this, first note that there are 2nordered pairs of complementary subsets A and B. In one case, A is empty, and in another B is empty, so 2n − 2 ordered pairs of subsets remain. Finally, since we want unordered pairs rather than ordered pairs we divide this last number by 2, giving the result above.
Another explicit expansion of the recurrence-relation gives identities in the spirit of the above example.
Identities
The table in section 6.1 of Concrete Mathematics provides a plethora of generalized forms of finite sums involving the Stirling numbers. Several particular finite sums relevant to this article include.
Explicit formula
The Stirling numbers of the second kind are given by the explicit formula:
This can be derived by using inclusion-exclusion to count the surjections from n to k and using the fact that the number of such surjections is .
Additionally, this formula is a special case of the kth forward difference of the monomial evaluated at x = 0:
The parity of a central Stirling number of the second kind is odd if and only if is a fibbinary number, a number whose binary representation has no two consecutive 1s.[11]
where are Touchard polynomials. If one sums the Stirling numbers against the falling factorial instead, one can show the following identities, among others:
and
which has special case
For a fixed integer k, the Stirling numbers of the second kind have rational ordinary generating function
A uniformly valid approximation also exists: for all k such that 1 < k < n, one has
where , and is the unique solution to .[14] Relative error is bounded by about .
Unimodality
For fixed , is unimodal, that is, the sequence increases and then decreases. The maximum is attained for at most two consecutive values of k. That is, there is an integer such that
Looking at the table of values above, the first few values for are
When is large
and the maximum value of the Stirling number can be approximated with
In particular, the nth moment of the Poisson distribution with expected value 1 is precisely the number of partitions of a set of size n, i.e., it is the nth Bell number (this fact is Dobiński's formula).
In other words, the nth moment of this probability distribution is the number of partitions of a set of size n into no more than m parts.
This is proved in the article on random permutation statistics, although the notation is a bit different.
Rhyming schemes
The Stirling numbers of the second kind can represent the total number of rhyme schemes for a poem of n lines. gives the number of possible rhyming schemes for n lines using k unique rhyming syllables. As an example, for a poem of 3 lines, there is 1 rhyme scheme using just one rhyme (aaa), 3 rhyme schemes using two rhymes (aab, aba, abb), and 1 rhyme scheme using three rhymes (abc).
Variants
r-Stirling numbers of the second kind
The r-Stirling number of the second kind counts the number of partitions of a set of n objects into k non-empty disjoint subsets, such that the first r elements are in distinct subsets.[15] These numbers satisfy the recurrence relation
Some combinatorial identities and a connection between these numbers and context-free grammars can be found in [16]
Associated Stirling numbers of the second kind
An r-associated Stirling number of the second kind is the number of ways to partition a set of n objects into k subsets, with each subset containing at least r elements.[17] It is denoted by and obeys the recurrence relation
The 2-associated numbers (sequence A008299 in the OEIS) appear elsewhere as "Ward numbers" and as the magnitudes of the coefficients of Mahler polynomials.
Reduced Stirling numbers of the second kind
Denote the n objects to partition by the integers 1, 2, ..., n. Define the reduced Stirling numbers of the second kind, denoted , to be the number of ways to partition the integers 1, 2, ..., n into k nonempty subsets such that all elements in each subset have pairwise distance at least d. That is, for any integers i and j in a given subset, it is required that . It has been shown that these numbers satisfy
(hence the name "reduced").[18] Observe (both by definition and by the reduction formula), that , the familiar Stirling numbers of the second kind.
^Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.
^Transformation of Series by a Variant of Stirling's Numbers, Imanuel Marx, The American Mathematical Monthly69, #6 (June–July 1962), pp. 530–532, JSTOR2311194.
^Antonio Salmeri, Introduzione alla teoria dei coefficienti fattoriali, Giornale di Matematiche di Battaglini 90 (1962), pp. 44–54.
^L. C. Hsu, Note on an Asymptotic Expansion of the nth Difference of Zero, AMS Vol.19 NO.2 1948, pp. 273--277
^N. M. Temme, Asymptotic Estimates of Stirling Numbers, STUDIES IN APPLIED MATHEMATICS 89:233-243 (1993), Elsevier Science Publishing.
^Broder, A. (1984). The r-Stirling numbers. Discrete Mathematics 49, 241-259
^Triana, J. (2022). r-Stirling numbers of the second kind through context-free grammars. Journal of automata, languages and combinatorics 27(4), 323-333
^L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
Scandinavian dessert Tilslørte bondepiker / bondepige med slørÄnglamat / Tilslørte bondepiker Bondepige med slørTypeDessertPlace of originScandinaviaMain ingredientsMashed fruit (apples or plums), whipped cream, bread- or rusk crumbs Media: Tilslørte bondepiker / bondepige med slør Verschleiertes Bauernmädchen served in a glass bowl Tilslørte bondepiker (lit. veiled peasant girls. Known in Swedish as änglamat; Danish: bondepige med slør; Norwegian: tilslørte bondepiker; Fin…
Gerd FaltingsGerd FaltingsLahir28 Juli 1954 (umur 69)Gelsenkirchen-Buer, Jerman BaratKebangsaanJermanAlmamaterUniversitas MünsterDikenal atas Konjektur Mordell Tinggi Faltings Teorema hasil kali Faltings PenghargaanMedali Fields (1986) Keanggotaan Guggenheim (1988)Penghargaan Leibniz (1996)Penghargaan Internasional Raja Faisal (2014) Penghargaan Shaw (2015) Medali Cantor (2017)Karier ilmiahBidangMatematikaInstitusiInstitut Max Planck untuk MatematikaUniversitas BonnUniversitas PrincetonUni…
Type of facial hair This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Chinstrap beard – news · newspapers · books · scholar · JSTOR (January 2017) (Learn how and when to remove this message) Paul Kruger with chinstrap beard General David Twiggs during the time of the Mexican–American War The chinstrap beard is …
Sugino Engineering CorporationNama asli株式会社スギノエンジニアリングJenisPrivat KKIndustriProduk rekreasiDidirikan(1910; 114 tahun lalu (1910))KantorpusatKota Nara, Prefektur Nara 630-8144, JapanProdukKomponen sepeda seperti :ChainringsCranksetsSitus webSitus web resmi Crankset Sugino XD Sugino (株式会社スギノエンジニアリングcode: ja is deprecated , Kabushiki-gaisha Sugino Enjiniaringu) adalah produsen komponen sepeda off-road dan roadbike Jepang. Perusah…
عمارة العصور الوسطى هو مصطلح يستخدم لوصف الطرز المعمارية المختلفة التي كانت منتشرة في العصور الوسطى.[1][2] كاتدرائية بيزا والبرج المائل بإيطاليا, أحد معالم الفترة الرومانسيكية بأوروبا العمارة الدينية و هي عمارة الكنائس والكاتدرائيات التي كانت منتشرة بشكل كبير في هذ…
لمعانٍ أخرى، طالع اتفاق باريس (توضيح). اتفاق باريس Accord de Parisمعلومات عامةالنوع معاهدة — بروتوكول بيئي جزء من اتفاقية الأمم المتحدة الإطارية بشأن التغير المناخي نسبة التسمية باريس التوقيع 12 ديسمبر 2015 (إقرار) 22 أبريل 2016 (توقيع)الموقعون القائمة ... الصين[1] — روسيا[…
伊斯兰合作组织Organisation of Islamic Cooperation(英語)Organisation de la Coopération Islamique(法語)منظمة التعاون الإسلامي(阿拉伯語) 旗帜格言:To safeguard the interests and ensure the progress and well-being of Muslims 成员国 观察国 暂停会籍行政总部 沙地阿拉伯吉达 官方语言阿拉伯语英语法语类型宗教成员国57个在籍成员国(英语:Member states of the Organisation of …
تازة كند جمال خان تقسيم إداري البلد إيران [1] إحداثيات 37°24′00″N 45°06′08″E / 37.4°N 45.1022°E / 37.4; 45.1022 الرمز الجغرافي 18506 تعديل مصدري - تعديل تازة كند جمال خان هي قرية في مقاطعة أرومية، إيران. عدد سكان هذه القرية هو 37 في سنة 2006.[2] مراجع ^ صفحة تازة ك…
Georgian square in London, England Fitzroy Square, view to the north from the Post Office Tower in 1967 The square in 2015 Entrance to 6 Fitzroy Square, headquarters of The Georgian Group A sculpture by Naomi Blake in Fitzroy Square Garden Virginia Woolf 1882-1941 Novelist and Critic lived here 1907–1911. Blue Plaque erected in 1974. Fitzroy Square is a Georgian square in London, England. It is the only one in the central London area known as Fitzrovia. The square is one of the area's main fea…
Habsburg siege and subsequent sack of Papal Rome For other uses, see Sack of Rome. This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (September 2021) (Learn how and when to remove this message) Sack of RomePart of the War of the League of CognacThe sack of Rome in 1527, by Johannes Lingelbach, 17th century (private collection)Date6 May 1527; 497 years agoLocationRo…
Online database about Australian literature AustLitHistory2000–LanguagesEnglish, Australian Aboriginal languagesAccessCostBy subscription; individuals may access it via their library. Limited guest access.CoverageDisciplinesAustralian literature: including criticism, bibliography, biographyGeospatial coverageAustraliaLinksWebsitewww.austlit.edu.au AustLit: The Australian Literature Resource (also known as AustLit: Australian Literature Gateway; and AustLit: The Resource for Australian Literatu…
Holocaust resource center in New Hampshire, US This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Cohen Center for Holocaust and Genocide Studies – news · newspapers · books…
Brazilian singer-songwriter For the Brazilian footballer, see Djavan (footballer). In this Portuguese name, the first or maternal family name is Caetano and the second or paternal family name is Viana. You can help expand this article with text translated from the corresponding article in Portuguese. (June 2024) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revis…
Disambiguazione – Se stai cercando il film di Carlo Vanzina, vedi Via Montenapoleone (film). Via Monte NapoleoneNomi precedentiv. Storia LocalizzazioneStato Italia CittàMilano CircoscrizioneMunicipio 1 Codice postale20121 Informazioni generaliTipostrada commerciale e attrazione turistica Lunghezza460 m IntitolazioneTrae il nome dal Monte Napoleone, che aveva sede al civico 12 CollegamentiLuoghi d'interesseQuadrilatero della moda Trasporti Montenapoleone San Babila Mappa Modifica dat…
Series of children's novels by Jill Murphy This article is about the novel series. For other uses, see The Worst Witch (disambiguation). The Worst WitchThe covers from the first seven books, shown in publication order.The Worst WitchThe Worst Witch Strikes AgainA Bad Spell for the Worst WitchThe Worst Witch All at SeaThe Worst Witch Saves the DayThe Worst Witch to the RescueThe Worst Witch and the Wishing StarFirst Prize for The Worst WitchAuthorJill MurphyIllustratorJill MurphyCover artistJill …
Испарение и конденсация на границе раздела пар-жидкость. При насыщении пара установлено динамическое равновесие между конденсацией и испарением, при этом в среднем число молекул, влетающих в жидкость, равно числу молекул вылетающих из жидкость в единицу времени. Насы́ще…