Nombres de Stirling de première espèce
Bonjour
En travaillant sur les nombres de Stirling de première espèce, je me suis rendu [compte] que l'on a pour $n \geq 2$ et $k \geq 2$,
$$S(n,k) = (n-1)! \sum_{1 \leq i_2<i_3<\dots<i_k \leq n-1} \frac{1}{i_2i_3 \dots i_k}.
$$ La démonstration que j'ai provient du fait qu'il y a autant de permutations ayant $k$ records que de permutations ayant $k$ cycles, le tout arrosé de v.a. dont l'indépendance est compliquée à prouver.
En consultant les documents classiques, je ne trouve pas cette formule pourtant très simple. Est-ce que ça parle à quelqu'un ? Est-ce un corollaire immédiat de formules obtenues par exemple ici : http://farhi.bakir.free.fr/index_fichiers/Stirling_1.pdf et qui m'aurait échappé ?
Merci pour vos idées.
edit : je me suis rendu compte tardivement que j'ai intitulé le message "nombre de Stirling de seconde espèce" alors qu'il s'agissait de ceux de première espèce, d'où le message de noix.de.totos
En travaillant sur les nombres de Stirling de première espèce, je me suis rendu [compte] que l'on a pour $n \geq 2$ et $k \geq 2$,
$$S(n,k) = (n-1)! \sum_{1 \leq i_2<i_3<\dots<i_k \leq n-1} \frac{1}{i_2i_3 \dots i_k}.
$$ La démonstration que j'ai provient du fait qu'il y a autant de permutations ayant $k$ records que de permutations ayant $k$ cycles, le tout arrosé de v.a. dont l'indépendance est compliquée à prouver.
En consultant les documents classiques, je ne trouve pas cette formule pourtant très simple. Est-ce que ça parle à quelqu'un ? Est-ce un corollaire immédiat de formules obtenues par exemple ici : http://farhi.bakir.free.fr/index_fichiers/Stirling_1.pdf et qui m'aurait échappé ?
Merci pour vos idées.
edit : je me suis rendu compte tardivement que j'ai intitulé le message "nombre de Stirling de seconde espèce" alors qu'il s'agissait de ceux de première espèce, d'où le message de noix.de.totos
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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)$.
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 !)...
Je vois que les nombres de Stirling de seconde espèce vous intéressent, voici mon humble contribution :
$\displaystyle \sum_{k = 1}^n k \cdot {n \choose k} \cdot k! \cdot S(n, k) = n(n^n - (n - 1)^n) $
avec comme conséquence immédiate :
$\displaystyle \lim_{n \to \infty} \dfrac{1}{n^{n + 1}} \sum_{k = 1}^n k \cdot {n \choose k} \cdot k! \cdot S(n, k) = 1 - \dfrac{1}{e}$
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.
successifs avec remise d'un numéro choisi parmi $n$. Chaque tirage étant indépendant des autres, et équiprobable.
Elle est donc équivalente à $n(1-e^{-1})$ quand $n$ tend vers l'infini.
Stirling -1 : (les valeurs absolues) A132393 de O.E.I.S.
Stirling - 2 : A048993 de O.E.I.S.
Stirling - 1 : [0, 1, 1, 2, 2, 3, 3, 4, 4, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]
Stirling - 2 : [0, 1, 0, 2, 0, 3, 0, 4, 0, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]
DELTA défini dans A084938.
Bien cordialement.
kolotoko