Nombres de Stirling de première espèce — Les-mathematiques.net The most powerful custom community solution in the world

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

Réponses

  • Relations entre racines et coefficients d'un polynôme + définition (ou propriété) $X(X+1)(X+2) \dots (X+n-1) = \sum_{k=1}^n S(n,k) X^k$ + un peu de bricolage et on y arrive, ouf !
  • 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)$.
  • Merci pour ta contribution. J'avais commis une boulette, ce sont les nombres de Stirling de première espèce ici dont je parlais et non de seconde espèce, mais peu importe, ton message m'apporte quelques relations supplémentaires sur les nombres de Stirling de seconde espèce qui m'intéressent aussi.
  • 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 !)...
  • Bonjour Gilles,

    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}$
  • 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 tombé sur cette formule en calculant l'espérance de la VA égale au nombre de numéros différents tirés lors de $n$ choix
    successifs avec remise d'un numéro choisi parmi $n$. Chaque tirage étant indépendant des autres, et équiprobable.
  • 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.
  • Bonjour,

    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
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!