| dbo:abstract
|
- In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one). 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 first kind. Identities linking the two kinds appear in the article on Stirling numbers in general. (en)
- Stirling-getallen van de eerste soort, genoemd naar de Schotse wiskundige James Stirling, komen voor in de combinatoriek en de studie van permutaties. (nl)
- В математиці , особливо в комбінаториці , числа Стерлінга першого роду виникають при вивченні перестановок. Зокрема, числа Стірлінга першого роду підраховують перестановки відповідно до їх кількості циклів (вважаючи нерухомі точки як цикли довжиною один). (uk)
- Числа Стирлинга первого рода (без знака) — количество перестановок из n элементов с k циклами. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageInterLanguageLink
| |
| dbo:wikiPageLength
|
- 44834 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:drop
| |
| dbp:proof
|
- These identities may be derived by enumerating permutations directly.
For example, a permutation of n elements with n − 3 cycles must have one of the following forms:
* n − 6 fixed points and three two-cycles
* n − 5 fixed points, a three-cycle and a two-cycle, or
* n − 4 fixed points and a four-cycle.
The three types may be enumerated as follows:
* choose the six elements that go into the two-cycles, decompose them into two-cycles and take into account that the order of the cycles is not important:
::
* choose the five elements that go into the three-cycle and the two-cycle, choose the elements of the three-cycle and take into account that three elements generate two three-cycles:
::
* choose the four elements of the four-cycle and take into account that four elements generate six four-cycles:
::
Sum the three contributions to obtain
: (en)
- We prove the recurrence relation using the definition of Stirling numbers in terms of permutations with a given number of cycles .
Consider forming a permutation of objects from a permutation of objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, i.e., leaving the extra object alone. This increases the number of cycles by 1 and so accounts for the term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of objects with cycles, and label the objects , so that the permutation is represented by
:
To form a new permutation of objects and cycles one must insert the new object into this array. There are ways to perform this insertion, inserting the new object immediately following any of the already present. This explains the term of the recurrence relation. These two cases include all possibilities, so the recurrence relation follows. (en)
- We prove the recurrence relation using the definition of Stirling numbers in terms of rising factorials. Distributing the last term of the product, we have
:
The coefficient of on the left-hand side of this equation is . The coefficient of in is , while the coefficient of in is . Since the two sides are equal as polynomials, the coefficients of on both sides must be equal, and the result follows. (en)
|
| dbp:title
|
- Combinatorial proof (en)
- Algebraic proof (en)
- Combinatorial proofs (en)
- Stirling numbers of the first kind, s (en)
|
| dbp:urlname
|
- stirlingnumbersofthefirstkind (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one). 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 first kind. Identities linking the two kinds appear in the article on Stirling numbers in general. (en)
- Stirling-getallen van de eerste soort, genoemd naar de Schotse wiskundige James Stirling, komen voor in de combinatoriek en de studie van permutaties. (nl)
- В математиці , особливо в комбінаториці , числа Стерлінга першого роду виникають при вивченні перестановок. Зокрема, числа Стірлінга першого роду підраховують перестановки відповідно до їх кількості циклів (вважаючи нерухомі точки як цикли довжиною один). (uk)
- Числа Стирлинга первого рода (без знака) — количество перестановок из n элементов с k циклами. (ru)
|
| rdfs:label
|
- Stirling-getallen van de eerste soort (nl)
- Stirling numbers of the first kind (en)
- Числа Стирлинга первого рода (ru)
- Число Стірлінга першого роду (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
.svg?width=300)
.svg){kind=link}
.svg){kind=link}