6.5 Quelques identités sur les nombres de Stirling et de Lah

Dans cette section, nous voulons étudier une formulation alternative des nombres de Stirling de première et de deuxième espèce, ainsi que des nombres de Lah. Cette formulation alternative nous est donnée sous la forme d’un ensemble de 7\displaystyle 7 identités qui ont des interprétations intéressantes en combinatoire. L’idée est la suivante. Nous savons déjà que les coefficients xn,xn¯\displaystyle x^{n},x^{\underline{n}} et xn¯\displaystyle x^{\overline{n}} jouent un rôle important en combinatoire. La question est maintenant de savoir s’il est possible d’écrire l’un d’eux à partir de l’autre.

Théorème 6.5.1:

Identités sur les nombres de Stirling et de Lah. Les principales relations entre les nombres de Stirling, les nombres de Lah, les factorielles montantes et les factorielles tombantes peuvent être résumer dans les 7\displaystyle 7 équations suivantes:

1.     xn=∑k=1n{nk}⁢xk¯\displaystyle x^{n}=\sum_{k=1}^{n}\left\{n\atop k\right\}x^{\underline{k}} 4.     xn=∑k=1n(−1)n+k⁢{nk}⁢xk¯\displaystyle x^{n}=\sum_{k=1}^{n}(-1)^{n+k}\left\{n\atop k\right\}x^{% \overline{k}}
2.     xn¯=∑k=1n[nk]⁢xk\displaystyle x^{\overline{n}}=\sum_{k=1}^{n}\left[n\atop k\right]x^{k} 5.     xn¯=∑k=1n(−1)n+k⁢[nk]⁢xk\displaystyle x^{\underline{n}}=\sum_{k=1}^{n}(-1)^{n+k}\left[n\atop k\right]x% ^{k}
3.     xn¯=∑k=1n⌊nk⌋⁢xk¯\displaystyle x^{\overline{n}}=\sum_{k=1}^{n}\left\lfloor n\atop k\right% \rfloor x^{\underline{k}} 6.     xn¯=∑k=1n(−1)n+k⁢⌊nk⌋⁢xk¯\displaystyle x^{\underline{n}}=\sum_{k=1}^{n}(-1)^{n+k}\left\lfloor n\atop k% \right\rfloor x^{\overline{k}}
7.⌊nk⌋=∑j=0n[nj]{jk}\displaystyle{\it 7.\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ }\left\lfloor n\atop k\right\rfloor=\sum_{j=0}^{n}\left[n\atop j% \right]\left\{j\atop k\right\}
Démonstration.
  1. 1.
    ​

    Nous avons déjà démontré cette égalité à l’aide de l’induction, mais nous présentons ici une démonstration différente basé sur un argument combinatorielle. La démonstration consiste à compter de deux manières différentes la même chose (double counting). Premièrement, rappelons que xn\displaystyle x^{n} représente le nombre de façon de placer n\displaystyle n objets différents dans x\displaystyle x urnes différentes sans aucune autre contrainte. Comme les urnes peuvent potentiellement être vide, alternativement, nous pouvons compter le nombre de façon de placer tous les objets dans une urne, dans deux urnes, etc jusqu’à x\displaystyle x urnes (sans qu’aucune de ces urnes soient vide), puis on additionne le tout. Pour placer les n\displaystyle n objets dans exactement k\displaystyle k urnes, on peut commencer par placer les n\displaystyle n objets distincts en k\displaystyle k groupes identiques sans qu’aucune urnes ne soit vide, ce qui se fait de {nk}\displaystyle\left\{n\atop k\right\}, puis ensuite placer chacun des k\displaystyle k groupes dans une des x\displaystyle x urnes avec ordre (car les urnes sont différentes) et sans remise (car nous ne voulons pas mettre plus qu’un groupe dans une urne). Ceci peut être accompli de xk¯\displaystyle x^{\underline{k}} façon. En additionnant le tout pour les différentes valeurs possible de k\displaystyle k, on obtient donc:

    xn=∑k=1n{nk}⁢xk¯\displaystyle x^{n}=\sum_{k=1}^{n}\left\{n\atop k\right\}x^{\underline{k}}
  2. 2.
    ​

    Nous allons faire cette démonstration par induction. Il est facile de vérifier que l’égalité est vrai pour n=1\displaystyle n=1, dans ce cas nous avons x=x\displaystyle x=x. Supposons que l’égalité est vrai pour n\displaystyle n, et nous allons montrer qu’elle est encore vrai pour n+1\displaystyle n+1. On a donc:

    ∑k=1n+1[n+1k]⁢xk\displaystyle\displaystyle\sum_{k=1}^{n+1}\left[n+1\atop k\right]x^{k} =\displaystyle\displaystyle= [n+11]⁢x+∑k=2n([nk−1]+n⁢[nk])⁢xk+[n+1n+1]⁢xn+1\displaystyle\displaystyle\left[n+1\atop 1\right]x+\sum_{k=2}^{n}\left(\left[n% \atop k-1\right]+n\left[n\atop k\right]\right)x^{k}+\left[n+1\atop n+1\right]x% ^{n+1}
    =\displaystyle\displaystyle= n!⁢x+∑k=2n[nk−1]⁢xk+n⁢∑k=2n[nk]⁢xk+xn+1\displaystyle\displaystyle n!x+\sum_{k=2}^{n}~\left[n\atop k-1\right]x^{k}+n% \sum_{k=2}^{n}\left[n\atop k\right]x^{k}+x^{n+1}
    =\displaystyle\displaystyle= n!⁢x+∑k=1n[nk]⁢xk+1+n⁢∑k=1n[nk]⁢xk−n⁢[n1]⁢x\displaystyle\displaystyle n!x+\sum_{k=1}^{n}\left[n\atop k\right]x^{k+1}+n% \sum_{k=1}^{n}\left[n\atop k\right]x^{k}-n\left[n\atop 1\right]x
    =\displaystyle\displaystyle= n!⁢x+x⁢∑k=1n[nk]⁢xk+n⁢∑k=1n[nk]⁢xk−n⁢(n−1)!⁢x\displaystyle\displaystyle n!x+x\sum_{k=1}^{n}\left[n\atop k\right]x^{k}+n\sum% _{k=1}^{n}\left[n\atop k\right]x^{k}-n(n-1)!x
    =\displaystyle\displaystyle= x⋅xn¯+n⋅xn¯=(x+n)⁢xn¯=xn+1¯\displaystyle\displaystyle x\cdot x^{\overline{n}}+n\cdot x^{\overline{n}}=(x+% n)x^{\overline{n}}=x^{\overline{n+1}}

    Ce qui complète notre démonstration.

  3. 3.
    ​

    La valeur xn¯\displaystyle x^{\overline{n}} représente le nombre de façon de placer n\displaystyle n objets différent dans k\displaystyle k urnes différentes, de sorte que l’ordre des objets dans les urnes soient importante. Remarquer que dans ce cas, les urnes peuvent possiblement être vide. Alternativement, on peut supposer que les objets sont placer dans exactement k\displaystyle k urnes (non-vide), et additionner pour les différentes valeurs possible de k\displaystyle k. Pour placer les objets dans exactement k\displaystyle k urnes, on peut commencer par diviser les n\displaystyle n objets en k\displaystyle k groupes identiques, de sorte que les objets dans chaque groupe soient ordonnés, ce qui peut être fait de ⌊nk⌋\displaystyle\left\lfloor n\atop k\right\rfloor façons, puis on choisit k\displaystyle k urnes parmi les x\displaystyle x avec ordre et sans remise dans lesquels placer nos groupes, ce qui peut être fait de xk¯\displaystyle x^{\underline{k}} façon. En additionnant le tout, on obtient:

    xn¯=∑k=1n⌊nk⌋⁢xk¯\displaystyle x^{\overline{n}}=\sum_{k=1}^{n}\left\lfloor n\atop k\right% \rfloor x^{\underline{k}}
  4. 4.
    ​

    L’idée de la démonstration est de remplacer x\displaystyle x par −x\displaystyle-x dans l’équation 1\displaystyle 1. Pour ce faire, remarquons premièrement que (−x)n=(−1)n⁢xn\displaystyle(-x)^{n}=(-1)^{n}x^{n}. De plus, nous avons:

    (−x)k¯=∏i=0k−1(−x−i)=∏i=0k−1(−1)⁢(x+i)=(−1)k⁢∏i=0k−1(x+i)=(−1)k⁢xk¯\displaystyle(-x)^{\underline{k}}=\prod_{i=0}^{k-1}(-x-i)=\prod_{i=0}^{k-1}(-1% )(x+i)=(-1)^{k}\prod_{i=0}^{k-1}(x+i)=(-1)^{k}x^{\overline{k}}

    En remplaçant dans l’équation 1\displaystyle 1 on obtient donc:

    (−1)n⁢xn=(−x)n=∑k=1n{nk}⁢(−x)k¯=∑k=1n{nk}⁢(−1)k⁢xk¯⇒xn=∑k=1n{nk}⁢(−1)k−n⁢xk¯=∑k=1n{nk}⁢(−1)k+n⁢xk¯\displaystyle(-1)^{n}x^{n}=(-x)^{n}=\sum_{k=1}^{n}\left\{n\atop k\right\}(-x)^% {\underline{k}}=\sum_{k=1}^{n}\left\{n\atop k\right\}(-1)^{k}x^{\overline{k}}% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ x^{n}=\sum_{k=1% }^{n}\left\{n\atop k\right\}(-1)^{k-n}x^{\overline{k}}=\sum_{k=1}^{n}\left\{n% \atop k\right\}(-1)^{k+n}x^{\overline{k}}

    Remarquez que a dernière égalité vient du fait que la valeur de (−1)i\displaystyle(-1)^{i} dépend seulement de la parité de i\displaystyle i.

  5. 5.
    ​

    L’idée est essentiellement la même que pour l’équation 4\displaystyle 4. La démonstration vous est laissé en exercice.

  6. 6.
    ​

    L’idée est essentiellement la même que pour l’équation 4\displaystyle 4. La démonstration vous est laissé en exercice.

  7. 7.
    ​

    Exercice

∎