Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Stirling numbers of the first kind
Résumé
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.
Stirling numbers of the first kind are the coefficients in the expansion of the falling factorial
into powers of the variable :
For example, , leading to the values , , and .
Subsequently, it was discovered that the absolute values of these numbers are equal to the number of permutations of certain kinds. These absolute values, which are known as unsigned Stirling numbers of the first kind, are often denoted or . They may be defined directly to be the number of permutations of elements with disjoint cycles. For example, of the permutations of three elements, there is one permutation with three cycles (the identity permutation, given in one-line notation by or in cycle notation by ), three permutations with two cycles (, , and ) and two permutations with one cycle ( and ). Thus, , and . These can be seen to agree with the previous calculation of for .
It was observed by Alfréd Rényi that the unsigned Stirling number also count the number
of permutations of size with left-to-right maxima.
The unsigned Stirling numbers may also be defined algebraically, as the coefficients of the rising factorial:
The notations used on this page for Stirling numbers are not universal, and may conflict with notations in other sources. (The square bracket notation is also common notation for the Gaussian coefficients.)
can be defined as the number of permutations on elements with cycles.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.