Nombre de Stirling

Introduction

En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIII siècle. Il en existe deux sortes, nommés les nombres de Stirling de première espèce et les nombres de Stirling de seconde espèce.

Notations

Diverses notations sont utilisées pour les nombres de Stirling, mais celles que l'on rencontre le plus souvent sont

$[n k]$ , pour les nombres de Stirling de première espèce, et

${n k}$ , pour les nombres de Stirling de seconde espèce.

Cette notation, analogue à celle utilisée pour les coefficients binomiaux, est due à Jovan Karamata (en), qui l'a proposée en 1935, et dont l'usage a été encouragé par Donald Knuth ; on l'appelle la notation de Karamata.

Nombres de Stirling de première espèce

En combinatoire, les nombres de Stirling de première espèce non signés comptent le nombre de permutations de n éléments se décomposant en k cycles disjoints. De manière plus générale, ces nombres sont les valeurs absolues des nombres de Stirling de première espèce (signés), qui sont les coefficients du développement de

(x) n = \sum k = 1^{n} [n k] x^{k}

où (x)_n est la factorielle décroissante

(x)_{n} = x (x - 1) (x - 2) \dots (x - n + 1) .

On peut inverser la définition afin d'exprimer x comme une suite de factorielles croissantes :

x^{n} = k = 0 \sum n [n k] (x)^{k}

Des relations similaires lient les nombres de Stirling de première espèce aux polynômes de Bernoulli. Un grand nombre de relations liées aux nombres de Stirling cachent des relations similaires liées aux coefficients binomiaux. L'étude des relations entre ces deux nombres est le calcul ombral et est un domaine important de la théorie des suites de Sheffer.

Table de valeurs

Voici une table donnant quelques valeurs des nombres de Stirling de première espèce, de la même forme que le triangle de Pascal:

n \ k

-1

-3

-6

-50

-10

-120

274

-225

-15

720

-1764

1624

-735

175

-21

-5040

13068

-13132

6769

-1960

322

-28

40320

-109584

118124

-67284

22449

-4536

546

-36

Relation de récurrence

Les nombres de Stirling de première espèce satisfont la relation de récurrence

[n + 1 k] = [n k - 1] - n [n k]

pour $1 \leq k \leq n - 1$ , avec les conditions initiales

[n 0] = 0 et [11] = 1

Ceci découle de la relation de récurrence des factorielles décroissantes :

$(x)_{n + 1} = x (x)_{n} - n (x)_{n}$ .

Identités simples

Remarquons que

[n 1] = (- 1)^{n - 1} (n - 1)!

[n n] = 1

[n n - 1] = (- 1)^{n} (2 n)

Il en existe d'autres, comme

[n 2] = (- 1)^{n} (n - 1)! H_{n - 1}

où H_n est un nombre harmonique et

[n 3] = \frac{1}{2} (- 1)^{n - 1} (n - 1)! [(H_{n - 1})^{2} - H_{n - 1}^{(2)}]

où $H_{n}^{(m)}$ est un nombre harmonique généralisé.

Formules explicites

On peut montrer la relation suivante entre nombres de Stirling de première et seconde espèce :

[n m] = k = 0 \sum n - m (- 1)^{k} (n - m + k n - 1 + k) (n - m - k 2 n - m) {n - m + k k},

d'où, utilisant la formule explicite pour ces derniers qui sera donnée plus bas :

[n m] = k = 0 \sum n - m j = 0 \sum k \frac{( - 1 ) ^{2 k - j}}{k !} (n - m + k n - 1 + k) (n - m - k 2 n - m) (j k) j^{n - m + k},

ou encore, après simplifications :

[n m] = \frac{( 2 n - m )!}{( m - 1 )!} k = 0 \sum n - m \frac{1}{( n + k ) ( n - m - k )! ( n - m + k )!} j = 0 \sum k \frac{( - 1 ) ^{j} j ^{n - m + k}}{j ! ( k - j )!} .

Fonction génératrice

Plusieurs identités peuvent être obtenues en manipulant la fonction génératrice

(1 + t)^{x} = n = 0 \sum \infty (n x) t^{n} = n = 0 \sum \infty \frac{t ^{n}}{n !} k = 0 \sum n [n k] x^{k} = k = 0 \sum \infty x^{k} n = k \sum \infty \frac{t ^{n}}{n !} [n k] = e^{x l n (1 + t)}

En particulier, l'ordre de la sommation peut être inversé; on peut également prendre des dérivées, ou encore fixer t ou x,

Sommes finies

k = 0 \sum n (- 1)^{k} [n k] = (- 1)^{n} n!

Sommes infinies

n = m \sum \infty [n k] \frac{x ^{n}}{n !} = \frac{( ln ( 1 + x ) ) ^{m}}{k !}

qui est valide pour x < 1.

Interprétation énumérative

La valeur absolue du nombre de Stirling de première espèce compte le nombre de permutations de n objets ayant exactement k cycles. Par exemple, $[42] = 11$ correspond au fait que le groupe symétrique S₄ possède trois permutations de la forme

( * * )( * * ) — 2 cycles de longueur 2

et huit permutations de la forme

( * * * ) — 1 cycle de longueur 3 et 1 cycle de longueur 1.

La valeur absolue du nombre de Stirling de première espèce compte aussi le nombre de permutations de n objets ayant exactement k records. Cette identité entre records et cycles résulte de la correspondance fondamentale de Foata. La forme produit de la série génératrice des nombres de Stirling de première espèce résulte de l'indépendance des termes du code de Lehmer d'une permutation, code très lié aux records d'une permutation.

Nombres de Stirling de seconde espèce

Les nombres de Stirling de seconde espèce ${n k}$ comptent le nombre de relations d'équivalence ayant k classes d'équivalence définies sur un ensemble de n éléments, c'est-à-dire aussi le nombre de partitions en k sous-ensembles d'un ensemble de n objets. La somme

B_{n} = k = 1 \sum n {n k}

est le n nombre de Bell. Si nous posons

(x)_{n} = x (x - 1) (x - 2) \dots (x - n + 1)

(en particulier, (x)₀ = 1 car il s'agit d'un produit vide) pour la factorielle décroissante, nous pouvons caractériser les nombres de Stirling de seconde espèce par

k = 0 \sum n {n k} (x)_{k} = x^{n} .

Table de valeurs

Voici quelques valeurs des nombres de Stirling de seconde espèce:

n \ k

301

350

140

127

966

1701

1050

266

255

3025

7770

6951

2646

462

Relation de récurrence

Ces nombres satisfont la relation de récurrence

{n k} = {n - 1 k - 1} + k {n - 1 k}

avec

${n 1} = 1 et {n n} = 1$ .

Identités simples

On a par exemple

{n n - 1} = (2 n)

{n 2} = 2^{n - 1} - 1

Formule explicite

Les nombres de Stirling de seconde espèce sont donnés par la formule explicite

${n k} = \frac{1}{k !} \sum_{j = 1}^{k} (- 1)^{k - j} (j k) j^{n}$ ,

laquelle s'obtient en remarquant que le nombre de surjections (d'un ensemble de n éléments vers un ensemble de k éléments) peut se compter par la formule d'inclusion-exclusion : on compte toutes les applications moins celles n'atteignant pas un certain élément, plus celles n'atteignant pas deux éléments, moins...

Rapport avec la distribution de Poisson

Si X est une variable aléatoire suivant une distribution de Poisson avec une moyenne λ, alors son n moment est

E (X^{n}) = k = 1 \sum n {n k} λ^{k} .

En particulier, le n moment d'une distribution de Poisson de moyenne 1 est précisément le nombre de partitions d'un ensemble de taille n, qui est le n nombre de Bell (formule de Dobinski).

Relation de réciprocité

Les nombres de Stirling de première et seconde espèce peuvent être considérés comme les inverses l'un de l'autre:

n = 0 \sum m a x {j, k} [n j] {k n} = δ_{j k}

n = 0 \sum m a x {j, k} {n j} [k n] = δ_{j k}

où δ_j**k est le symbole de Kronecker.