Nombres de Stirling de première espèce

Il y a deux ans, je suis tombé sur ces nombres, de façon inattendue, alors que je travaillais sur un analogue unitaire de la matrice de Redheffer.

Voici quelques résultats annexes que j'ai pu dégoter, pour lesquels je reprend la notation de Knuth $\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ avec $k \leqslant n$.

(i) Quelques valeurs.
$$\left\{ \begin{array}{c} n \\ 0 \end{array} \right\} = \begin{cases} 1, & \textrm{si} \ n=0 \\ 0, & \textrm{sinon} \end{cases}, \quad \left\{ \begin{array}{c} n \\ 1 \end{array} \right\} = \left\{ \begin{array}{c} n \\ n \end{array} \right\} = 1, \quad \left\{ \begin{array}{c} n \\ 2 \end{array} \right\} = 2^{n-1}-1$$
$$\left\{ \begin{array}{c} n \\ 3 \end{array} \right\} = \tfrac{1}{6} \left( 3^n - 3 \times 2^n + 3 \right), \quad \left\{ \begin{array}{c} n \\ 4 \end{array} \right\} = \tfrac{1}{6} \left( 4^{n-1} - 3^n + 3 \times 2^{n-1} - 1 \right), \quad \left\{ \begin{array}{c} n \\ n-1 \end{array} \right\} = {n \choose 2}.$$

(ii) Formules de récurrence.
$$\left\{ \begin{array}{c} n+1 \\ k \end{array} \right\} = \left\{ \begin{array}{c} n \\ k-1 \end{array} \right\} + k \left\{ \begin{array}{c} n \\ k \end{array} \right\}.$$
$$\left\{ \begin{array}{c} n \\ k \end{array} \right\} = \sum_{j=k-1}^{n-1} {n \choose j} \left\{ \begin{array}{c} j \\ k - 1 \end{array} \right\}.$$
$$\left\{ \begin{array}{c} n \\ k \end{array} \right\} =\sum_{j=1}^k j \left\{ \begin{array}{c} n+j-k \\ j \end{array} \right\} \quad \left( k+1 \leqslant n \right).$$

(iii) Expression explicite directe.
$$k! \left\{ \begin{array}{c} n \\ k \end{array} \right\} = \sum_{n_1 + \dotsb + n_k = n} {n \choose n_1, \dotsc,n_k}.$$

(iv) Inégalités.
$$\left\{ \begin{array}{c} n \\ k \end{array} \right\} \leqslant \frac{k^{n-1}}{(k-1)!}.$$
$$\tfrac{1}{2} (k^2+k+2)k^{n-k-1} - 1 \leqslant \left\{ \begin{array}{c} n \\ k \end{array} \right\} \leqslant \frac{1}{2} {n \choose k} k^{n-k} \quad \left( n \geqslant 2, \ 1 \leqslant k \leqslant n-1 \right).$$
$$\left\{ \begin{array}{c} n \\ k \end{array} \right\}^2 \geqslant \left\{ \begin{array}{c} n \\ k-1 \end{array} \right\} \times \left\{ \begin{array}{c} n \\ k +1\end{array} \right\}.$$

(v) Propriétés arithmétiques. On considère un nombre premier $p$.

$\triangleright$ Pour tout $k \in \{2,\dotsc,p-1\}$, $p$ divise $\left\{ \begin{array}{c} p \\ k \end{array} \right\}$ et $p$ ne divise ni $\left\{ \begin{array}{c} p \\ 1 \end{array} \right\}$, ni $\left\{ \begin{array}{c} p \\ p \end{array} \right\}$.

$\triangleright$ $\left\{ \begin{array}{c} p+1 \\ 2 \end{array} \right\} \equiv 1 \; \left(\textrm{mod} \; p \right)$.

Oui, tu as raison, il vaut mieux insister pour ceux qui liront ce sujet : mon message porte sur les nombres de Stirling de seconde espèce (tel qu'indiqué dans une première version du titre de ce fil).

Comme je l'ai dit plus haut, ça a été une vraie surprise pour moi de les trouver là où je ne les attendais pas du tout (mais alors, pas du tout !)...

L'égalité peut se démontrer avec un raisonnement combinatoire si on l'écrit $n^n = (n - 1)^n+\displaystyle \sum_{k = 1}^n {n-1 \choose k-1} \rm{Surj}(n, k) $ où $\rm{Surj}(n, k)=k!\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ est le nombre de surjections de $1,n$ vers $1,k$.

Les $n^n$ applications de $1,n$ vers $1,n$ se répartissent en $(n-1)^n$ applications de $1,n$ vers $1,n-1$ et les applications pour lesquelles $n$ est dans l'image.

Ces dernières sont au nombre de $\displaystyle \sum_{k = 1}^n {n-1 \choose k-1} \rm{Surj}(n, k) $ car il faut choisir les $k-1$ éléments autres que $n$ dans l'image.

Je suis d'accord, l'espérance de $X$ est égale à la valeur commune aux deux membres de l'égalité divisée par $n^n$.

Elle est donc équivalente à $n(1-e^{-1})$ quand $n$ tend vers l'infini.