Stirling 2 – Le retour

Sortez les popcorns et installez-vous confortablement dans votre siège. C’est l’heure des frissons.

Trailer

La scène se passe dans un grand manoir situé au milieu d’une forêt américaine. Un groupe de 10 jeunes personnes alcoolisées s’est réuni pour passer le week-end afin de célébrer les vacances de Printemps. Mais la nuit venue, des bruits étranges se font entendre dans les couloirs de la maison…

Ce que ces jeunes gens ignorent, c’est que 40 ans plutôt ce manoir a été le lieu d’un fait divers des plus sordides. Une famille toute entière avait alors été retrouvée ensevelie sous des hectolitres de beurre de cacahuète. La légende raconte depuis lors que cette maison est hantée par une cacahuète géante et communiste.

Comme dans tout bon film d’horreur américain, ces jeunes gens décident de se séparer en groupes en attendant que le jour se lève. On sait bien de toute façon que chaque groupe se fera tour à tour massacré lamentablement pendant la nuit, là n’est pas la question (j’ai même envie de dire que c’est uniquement pour cette raison qu’on a payé notre place de ciné). Ce qu’on peut se demander ici est plutôt: si ces 10 personnes décident de former trois groupes (chaque groupe n’étant pas nécessairement de la même taille),  de combien de façons peuvent-elles le faire ?

Nombre de Stirling de seconde espèce

On peut reformuler la question ainsi: « A  partir de 10 objets numérotés, combien y a-t-il de façons de former trois tas (non numérotés, les tas) ? ». Mathématiquement, cette question s’énonce de la façon suivante: « Combien y a-t-il de partitions d’un ensemble à 10 éléments en 3 sous-ensembles ? ».

Plus généralement, combien y a-t-il de partitions d’un ensemble à n éléments en k sous-ensembles ? Ce nombre de partitions possibles s’appelle nombre de Stirling de seconde espèce. On le note . Nous allons tenter de l’étudier dans cet article.

Quelques cas particuliers pour comprendre

Tout d’abord, il est clair que car il y une seule façon de former un groupe à partir d’une personne. De même, pour tout entier naturel n non nul. Ensuite, il est aussi évident que si k>n alors (comment voulez-vous former plus de groupes qu’il n’y a de personnes ?).

Voyons ce qu’il se passe pour quelques valeurs petites de n et de k:

Il y a trois façons de former deux tas à partir de trois objets numérotés donc S(3,2)=3.

S(4,3)=6

Enfin, voici une table des premières valeurs de S(n,k) représentées dans le jeu vidéo Minecraft (avec l’aide du mod Computercraft qui permet d’entrer des programmes codés en Lua):

Oui, je sais, j’aurais pu tout simplement faire un tableau sur Excel comme tout le monde mais je trouvais ça beaucoup plus amusant. Au passage, ce tableau nous donne la réponse à la question de départ: il y a 9330 possibilités de répartir les 10 jeunes gens en trois groupes.

Le calcul des termes de cette suite a été fait grâce aux propriétés que nous allons démontrer ci-dessous.

Etude de la suite S(n,k)

Un peu comme nous avions fait lorsqu’on nous avions calculé la probabilité que le Père Noel se trompe, nous allons déterminer une relation de récurrence satisfaite par la suite . Grossièrement, nous allons exprimer le nombre de partitions d’un ensemble à n éléments à partir du nombre de partitions d’un ensemble à n-1 éléments.

Considérons donc objets que nous devons répartir en groupes. Nous distinguons deux cas:

1. Si l’objet numéroté est tout seul dans son groupe, il faut donc répartir les autres objets dans les autres groupes, ce qui donne possibilités par définition.
2. Si l’objet numéroté n’est pas seul dans son groupe alors placer les objets revient à d’abord placer les premiers objets dans les groupes (ce qui donne possibilités) puis à placer l’objet dans un des groupes (ce qui donne possibilités). Au total, cela fait donc possibilités.

Puisque ces deux cas sont disjoints, nous avons donc prouvé que

Cette relation de récurrence permet de calculer facilement les valeurs de la suite à la manière du triangle de Pascal. En effet, cette relation dit que pour calculer le nombre situé dans la ligne et la colonne , il faut ajouter le nombre situé dans la case située en haut à sa gauche avec le produit de la case située juste au-dessus avec le numéro de la colonne. Dit comme cela, ça ne paraît sans doute pas très clair donc voici un schéma expliquant le calcul de :

Le calcul des nombres de Stirling est très proche du calcul des coefficients binomiaux dans le triangle de Pascal. Ici, S(10,4) = 255 + 3×3025 = 9330

Pour les flemmards qui préfèrent laisser à la machine le soin de calculer, sachez que cette relation de récurrence se programme très facilement. Voici le code en Lua pour calculer :

function Stirling(n,k)
if k>n then
return 0
elseif (k==n) or (k==1) then
return 1
else
return Stirling(n-1,k-1) + k*Stirling(n-1,k)
end
end

print(« Stirling(10,3) =  » .. tostring(Stirling(10,3))

Et voici le résultat:

Forme explicite de S(n,k)

Il est possible d’exprimer S(n,k) directement à partir de n et k. Plus précisément, voici la formule que nous allons démontrer (valable pour tout et pour tout ) :

Toutes les démonstrations que j’ai pu voir sur Internet utilisaient la formule du crible de Poincaré (encore appelée principe d’inclusion-exclusion). Mais on dispose d’une relation de récurrence vérifiée par cette suite, donc autant utiliser un raisonnement par récurrence. La démonstration par récurrence étant assez technique et lourde en notations, je l’ai mise dans le pdf ci-dessous. Je lance quand même une alerte au calcul imbitable… Je vous aurais prévenus !

Preuve de la formule explicite

Ouf !

Groupes numérotés

A présent, on suppose que les groupes ne sont plus indiscernables mais qu’ils sont chacun bien spécifiés. Par exemple, imaginons que nos 10 jeunes gens se séparent en trois groupes de la façon suivante: le groupe qui va se réfugier dans la cave (appelé groupe n°1), le groupe qui va se planquer au grenier (groupe 2) et le groupe qui va se cacher dans la chambre (groupe 3). Combien y a-t-il alors de façons de répartir ces 10 personnes dans ces trois groupes ? En fait, placer dix objets numérotés dans trois boites numérotées revient à compter le nombre de surjections d’un ensemble à 10 éléments dans un ensemble à 3 éléments.

Pour placer objets numérotés dans groupes numérotés, on commence par choisir une configuration de répartition de ces objets (ce qui donne possibilités) puis à choisir un numéro pour chacun des groupes (il y a possibilités, autrement dit autant de possibilités qu’il y a de permutations possibles de ces groupes). Ainsi, le nombre de façons de répartir objets numérotés n groupes numérotés est . C’est donc aussi le nombre de surjections d’un ensemble à n éléments dans un ensemble à k éléments.

En particulier, il y a possibilités de répartir nos 10 jeunes gens en trois groupes numérotés. Mais bon, le temps qu’ils essayent toutes les combinaisons, la cacahuète géante aura déjà eu largement le temps de tous les attraper…. Vraiment n’importe quoi cet article décidémment !

Note

Vous aurez sans doute reconnu dans le début de cet article une référence au sketch de Jean-Marie Bigard sur les films d’horreur.

Liens

Les nombres de Stirling sur Wikipedia.

Site officiel du langage de programmation Lua.

Site officiel du jeu Minecraft.

Publicité