6.3 Nombres de Stirling de première espèce

Avant de définir et d’étudier les nombres de Stirling de première espèce, commençons par regarder quelques exemples relativement simple que nous avons déjà considéré au chapitre 1.

Exemple 6.3.1.

De combien de façons peut-on placer n\displaystyle n personnes sous forme d’un rang ? Par le principe du produit, nous savons que ceci peut-être accompli de n!\displaystyle n! façons.

Exemple 6.3.2.

De combien de façons peut-on assoir n\displaystyle n personnes autour d’une table ronde ? Par le principe du produit, nous savons qu’il y a n!\displaystyle n! façons d’assoir les n\displaystyle n personnes. Cependant, en considérant que chacune des n\displaystyle n rotations de la table nous donne une configuration équivalente, par le principe d’équivalence, le nombre de possibilité est:

n!n=(n−1)!\displaystyle\frac{n!}{n}=(n-1)!
Exemple 6.3.3.

De combien de façons peut-on assoir un groupe de 20\displaystyle 20 personnes autour de 2\displaystyle 2 tables rondes si chacune des deux tables doit contenir exactement 10\displaystyle 10 personnes ? Dans ce cas, on commence par choisir les 10\displaystyle 10 personnes qui seront sur la première table, ce qui peut être fait de (2010)\displaystyle\binom{20}{10} façons, puis on les places à chacune des 2\displaystyle 2 tables, ce qui peut être fait de 9!\displaystyle 9! façons (pour chacune des tables), et finalement comme les deux tables sont identiques, on doit diviser le tout par 2!\displaystyle 2!. On a donc:

(2010)⁢(9!)22!=20!⋅9!⋅9!10!⋅10!⋅2!=20!200\displaystyle\binom{20}{10}\frac{(9!)^{2}}{2!}=\frac{20!\cdot 9!\cdot 9!}{10!% \cdot 10!\cdot 2!}=\frac{20!}{200}

façons d’assoir les 20\displaystyle 20 personnes.

L’exemple précédent peut facilement se généraliser à k\displaystyle k personnes que l’on souhaite assoir autour de n\displaystyle n tables rondes de sorte que chaque table contiennent le même nombre de personnes. Les nombres de Stirling de première espèce est en quelques sortes une généralisation supplémentaire de l’exemple précédent. On peut énoncer le problème comme suit:

De combien de façons peut-on placer k\displaystyle k personnes autours de n\displaystyle n tables rondes identiques sans qu’aucune table ne soit laisser vide ?

La difficulté vient du fait que le nombre de personnes autour de chaque table n’est pas fixe. La seule contrainte est qu’aucune table ne peut être laissé vide. Nous allons donc définir la solution du problème comme étant le nombre de Stirling de première espèce [kn]\displaystyle\left[k\atop n\right]. Une formule explicite pour ces nombre est hors de ne porté (votre professeur n’en connait d’ailleurs aucune), mais il est tout de même relativement simple de les définir à partir d’une relation de récurrence.

[kn]=[k−1n−1]+(k−1)⁢[k−1n] si ⁢1<n<k\displaystyle\left[k\atop n\right]=\left[k-1\atop n-1\right]+(k-1)\left[k-1% \atop n\right]\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \textrm{ si }1<n<k

À cette relation, nous devons ajouter les conditions initiales suivantes:

[k1]=(k−1)!,[kk]=1 et [kn]=0⁢ si ⁢k<n\displaystyle\left[k\atop 1\right]=(k-1)!,\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \left% [k\atop k\right]=1\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{ et }\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \left[k\atop n\right]=0\textrm{ si }k<n

Remarquez que notre première valeur initiale n’est en fait rien d’autre que la solution au premier exemple de cette section. À partir de notre récurrence, il est maintenant facile d’utiliser Python pour construire une table de valeurs.

Listing 29: Nombres de Stirling de première espèce
⬇

              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def Stirling1(k,n):


              6
              
              
              
                if n == 1:


              7
              
              
              
                    return factorial(k-1)


              8
              
              
              
                if k == n:


              9
              
              
              
                    return 1


              10
              
              
              
                if k < n:


              11
              
              
              
                    return 0


              12
              
              
              
                else:


              13
              
              
              
                    return Stirling1(k-1,n-1) + (k-1) * Stirling1(k-1,n)


              14
              
              
              
            


              15
              
              
              
            A = []


              16
              
              
              
            for k in range(1,11):


              17
              
              
              
                ligne = [Stirling1(k,n) for n in range(1,11)]


              18
              
              
              
                A.append(ligne)


              19
              
              
              
            tableau = DataFrame(A)


              20
              
              
              
            tableau.index = [i for i in range(1,11)]


              21
              
              
              
            tableau.columns = [i for i in range(1,11)]


              22
              
              
              
            tableau

Nombres de Stirling de première espèce

k\n\displaystyle k\backslash n 1 2 3 4 5 6 7 8 9 10
1 1 0 0 0 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0 0 0
3 2 3 1 0 0 0 0 0 0 0
4 6 11 6 1 0 0 0 0 0 0
5 24 50 35 10 1 0 0 0 0 0
6 120 274 225 85 15 1 0 0 0 0
7 720 1764 1624 735 175 21 1 0 0 0
8 5040 13068 13132 6769 1960 322 28 1 0 0
9 40320 109584 118124 67284 22449 4536 546 36 1 0
10 362880 1026576 1172700 723680 269325 63273 9450 870 45 1