matrice de Stirling

Prenons quatre objets étiquetés. On peut soit les répartir en deux groupes non vides, soit les permuter en imposant exactement deux cycles. Ces deux questions donnent respectivement 7 et 11 possibilités.

Une matrice de Stirling range systématiquement ces comptages : la ligne indique le nombre d'objets et la colonne le nombre de groupes ou de cycles. Sa forme triangulaire vient d'une contrainte visible : quatre objets ne peuvent pas former plus de quatre groupes non vides ni plus de quatre cycles.

Pour deux entiers naturels i et j, le nombre S(i, j) de deuxième espèce compte les partitions d'un ensemble de i éléments en j parties non vides. Le nombre c(i, j) de première espèce compte les permutations de i éléments ayant j cycles. Une troncature aux indices compris entre 0 et N place ces nombres à la ligne i et à la colonne j. Comme j ne peut pas dépasser i, tous les coefficients au-dessus de la diagonale sont nuls : la matrice est triangulaire inférieure.

La matrice de deuxième espèce contient les S(i, j). Pour obtenir son inverse, il faut employer les nombres de première espèce signés, notés s(i, j). Ils se déduisent des comptages non signés c(i, j) par la règle :

La matrice S de deuxième espèce et la matrice s de première espèce signée sont inverses pour la convention ligne-degré, colonne-indice. Pour des indices i et k, leur produit vérifie :

Ici, δ vaut 1 lorsque i égale k et 0 sinon. Cette inversion traduit un changement de base. Si le polynôme factoriel descendant de degré k est le produit x(x − 1)…(x − k + 1), alors :

Une matrice de Stirling réunit quatre éléments nécessaires. Les lignes portent le nombre i d'objets. Les colonnes portent le nombre j de cycles ou de parties. Les coefficients donnent les comptages S(i, j), c(i, j) ou leur version signée s(i, j). La diagonale ne contient que des 1 : il existe une seule partition en autant de singletons que d'objets et une seule permutation formée uniquement de cycles d'un élément.

Le choix de l'espèce fixe donc le sens combinatoire des coefficients, tandis que le choix signé ou non signé fixe la propriété d'inversion. L'indice maximal N fixe la taille de la troncature : avec les indices 0 à N, elle comporte N + 1 lignes et N + 1 colonnes. Ces données suffisent à construire la matrice, à lire un comptage et à effectuer le changement entre puissances ordinaires et factorielles descendantes.

Construisons les troncatures d'indices 0 à 4 et contrôlons un coefficient de leur produit. Les deux matrices réunissent les mêmes degrés, mais la première espèce porte ici les signes nécessaires à l'inversion.

Données.
Indice maximal : N = 4.
Deuxième espèce, ligne 4 : 0, 1, 7, 6, 1.
Première espèce signée, colonne 2 aux lignes 2, 3 et 4 : 1, −3, 11.
Coefficient à contrôler : ligne 4, colonne 2 du produit.

Étape 1. Dans le produit, seuls les indices intermédiaires 2, 3 et 4 contribuent au coefficient choisi.

Étape 2. Multiplions les termes correspondants, puis additionnons-les :

Étape 3. Le résultat attendu est bien 0, car la position (4, 2) se trouve hors de la diagonale de la matrice identité.

Contrôle. Sur la diagonale, la position (4, 4) donne 1 × 1 = 1. Les deux vérifications retrouvent donc les valeurs 0 et 1 imposées par l'identité.

Pour développer une puissance dans la base des factorielles descendantes, on lit une ligne de la matrice de deuxième espèce. Ainsi, la ligne 4 donne les coefficients 1, 7, 6 et 1 pour les degrés 1 à 4. Un développement direct reste possible pour un seul petit degré ; la matrice devient préférable quand plusieurs degrés doivent être convertis.

Pour revenir des factorielles descendantes aux puissances ordinaires, on emploie la matrice de première espèce signée. Le critère décisif est le sens du changement de base : l'aller utilise S(i, j), le retour utilise s(i, j), avec ses signes.

En combinatoire énumérative, le choix dépend de l'objet compté. Des groupes non vides appellent la deuxième espèce ; des permutations classées par nombre de cycles appellent la première. Pour quatre objets et deux composantes, cette distinction sépare les 7 partitions des 11 permutations.

Un nombre de Stirling. Il s'agit d'un coefficient isolé, déterminé par deux indices. Une matrice de Stirling rassemble un ensemble ordonné de ces coefficients. Par exemple, 7 est le nombre S(4, 2), tandis que la troncature d'indices 0 à 4 est une matrice de 25 positions.

Première et deuxième espèces. Le test porte sur ce qui est compté. Avec quatre éléments et deux composantes, la deuxième espèce compte 7 partitions en deux parties non vides ; la première compte 11 permutations ayant deux cycles.

La formule de Stirling. Cette formule concerne une approximation de la factorielle, pas une matrice de changement de base. La présence du même nom ne suffit donc pas : ici, les indices comptent des cycles ou des parties.

Oublier les signes. La matrice des nombres c(i, j), tous non négatifs, n'est pas l'inverse de la matrice de deuxième espèce. Le symptôme est un produit non diagonal. Il faut remplacer c(i, j) par s(i, j), dont le signe alterne selon i − j.

Confondre ordre et indice maximal. Une matrice indexée de 0 à N possède N + 1 lignes. Si « ordre N » désigne au contraire une matrice N × N, le dernier indice est N − 1. Il faut annoncer la plage d'indices avant de comparer deux troncatures.

Négliger le cas vide. La convention combinatoire donne S(0, 0) = c(0, 0) = 1. Pour i strictement positif, aucun découpage en zéro partie et aucune permutation en zéro cycle ne sont comptés : les coefficients de colonne 0 valent alors 0.

Changer l'orientation. Ici, les lignes portent i et les colonnes j. Une convention transposée échange cette lecture et transpose les matrices. Avant une multiplication, il faut vérifier l'ordre des indices et le sens du changement de base.

Le glossaire nombre de Stirling approfondit les coefficients individuels avant leur organisation en matrice.

La fiche partition d'un ensemble précise l'objet combinatoire compté par les nombres de deuxième espèce.