Nombre De Stirling

Nombre De Stirling

Nombre de Stirling

En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIIIe siècle. Il en existe deux sortes, nommés les nombres de Stirling de première espèce et les nombres de Stirling de seconde espèce.

Sommaire

Notations

Diverses notations sont utilisées pour les nombres de Stirling, mais celles que l'on rencontre le plus souvent sont

\left[\begin{matrix} n \\ k \end{matrix}\right], pour les nombres de Stirling de première espèce, et
\left\{\begin{matrix} n \\ k \end{matrix}\right\}, pour les nombres de Stirling de seconde espèce.

Cette notation, analogue à celle utilisée pour les coefficients binomiaux, est due à Jovan Karamata qui l'a proposée en 1935, et dont l'usage a été encouragé par Donald Knuth ; on l'appelle la notation de Karamata.

Nombres de Stirling de première espèce

En combinatoire, les nombres de Stirling de première espèce non signés comptent le nombre de permutations de n éléments se décomposant en k cycles disjoints. De manière plus générale, ces nombres sont les valeurs absolues des nombres de Stirling de première espèce (signés), qui sont les coefficients du développement de

(x)_n=\sum_{k=1}^n \left[\begin{matrix} n \\ k \end{matrix}\right]x^k

où (x)n est la factorielle décroissante

(x)_n=x(x-1)(x-2)\cdots(x-n+1).

On peut inverser la définition afin d'exprimer xn comme une suite de factorielles croissantes :

x^n = \sum_{k=0}^n \left[\begin{matrix} n \\ k \end{matrix}\right] (x)^k

Des relations similaires lient les nombres de Stirling de première espèce aux polynômes de Bernoulli. Un grand nombre de relations liées aux nombres de Stirling cachent des relations similaires liées aux coefficients binomiaux. L'étude des relations entre ces deux nombres est le calcul ombral et est un domaine important de la théorie des suites de Sheffer.

Table de valeurs

Voici une table donnant quelques valeurs des nombres de Stirling de première espèce, de la même forme que le triangle de Pascal:

n \ k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 -1 1
3 0 2 -3 1
4 0 -6 11 -6 1
5 0 24 -50 35 -10 1
6 0 -120 274 -225 85 -15 1
7 0 720 -1764 1624 -735 175 -21 1
8 0 -5040 13068 -13132 6769 -1960 322 -28 1
9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1

Relation de récurrence

Les nombres de Stirling de première espèce satisfont la relation de récurrence

\left[\begin{matrix} n+1 \\ k \end{matrix}\right] = 
\left[\begin{matrix} n \\ k-1 \end{matrix}\right]
-n \left[\begin{matrix} n \\ k \end{matrix}\right]

pour 1\leq k\leq n-1, avec les conditions initiales

\left[\begin{matrix} n \\ 0 \end{matrix}\right]=0 
\quad \mbox { et } \quad
\left[\begin{matrix} 1 \\ 1 \end{matrix}\right] = 1

Ceci découle de la relation de récurrence des factorielles décroissantes :

(x)_{n+1} = x(x)_n - n(x)_n\,.

Identités simples

Remarquons que

\left[\begin{matrix} n \\ 1 \end{matrix}\right] = 
(-1)^{n-1} (n-1)!

et

\left[\begin{matrix} n \\ n \end{matrix}\right] = 1

et

\left[\begin{matrix} n \\ n-1 \end{matrix}\right] = (-1)^n
{n \choose 2}

Il en existe d'autres, comme

\left[\begin{matrix} n \\ 2 \end{matrix}\right] = 
(-1)^n (n-1)!\; H_{n-1}

Hn est un nombre harmonique et

\left[\begin{matrix} n \\ 3 \end{matrix}\right] = 
\frac {1}{2} (-1)^{n-1} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]

H_n^{(m)} est un nombre harmonique généralisé.

Formule explicite

s(n,k) = (-1)^{n-k}
                \times \frac{n!}{2^{n-k} (k-1)!}
 \times \left [ \sum_{i=1}^{n-k} (-1)^{i-1} \left \{
               \left ( \frac{1}{6^{i-1} (i-1)! (n-k-2i+2)!} \right ) 
             - \left ( \frac{(i-3)}{5 \times 6^{i-2} (i-3)! (n-k-2i+4)!} \right ) 
             + \left ( \frac{(i-5)(21i-46)}{1050 \times 6^{i-3} (i-5)! (n-k-2i+6)! }\right )
             - \left ( \frac{(i-7)(i-4)(7i-11)}{5250 \times 6^{i-4} (i-7)! (n-k-2i+8)!} \right )
             + \left ( \frac{(i-9) \times 6 \left ( 5040+2959 C(i-10,1) + \cdots \right ) }
                            {1819125 \times 6^{i-5} (i-9)! (n-k-2i+10)!} \right )
             - \cdots
               \right \}
               \times n^{n-k-i} \right ]


s(n,k) = (-1)^(n-k) × ( n!/{(k-1)!×2^(n-k)} ) 
       × [ Sum_{i=1..n-k} (-1)^(i-1) × {
         ( 1/{6^(i-1)×(i-1)!×(n-k-2×i+2)!} )
       - ( {(i-3)}/{5×6^(i-2)×(i-3)!×(n-k-2×i+4)!} )
       + ( {(i-5)×(21×i-46)}/{1050×6^(i-3)×(i-5)!×(n-k-2×i+6)!} )
       - ( {(i-7)×(i-4)×(7×i-11)}/{5250×6^(i-4)×(i-7)!×(n-k-2×i+8)!} )
       + (   {(i-9)×6×(5040+2959×C(i-10,1)+...)}/{1819125×6^(i-5)×(i-9)!×(n-k-2×i+10)!} )
       - .....
      }×n^(n-k-i) ].

Fonction génératrice

Plusieurs identités peuvent être obtenues en manipulant la fonction génératrice

(1+t)^x = \sum_{n=0}^\infty {x \choose n} t^n = 
\sum_{n=0}^\infty \frac {t^n}{n!} \sum_{k=0}^n 
\left[\begin{matrix} n \\ k \end{matrix}\right] x^k = 
\sum_{k=0}^\infty x^k
\sum_{n=k}^\infty \frac {t^n}{n!}
\left[\begin{matrix} n \\ k \end{matrix}\right] = 
e^{x\ln(1+t)}

En particulier, l'ordre de la sommation peut être inversé; on peut également prendre des dérivées, ou encore fixer t ou x,

Sommes finies

\sum_{k=0}^n (-1)^k 
\left[\begin{matrix} n \\ k \end{matrix}\right] = 
(-1)^n n!

Sommes infinies

\sum_{n=m}^\infty 
\left[\begin{matrix} n \\ k \end{matrix}\right] 
\frac{x^n}{n!} = \frac {\left(\ln (1+x)\right)^m}{k!}

qui est valide pour x < 1.

Interprétation énumérative

La valeur absolue du nombre de Stirling de première espèce compte le nombre de permutations de n objets ayant exactement k cycles. Par exemple, \left[\begin{matrix} 4 \\ 2 \end{matrix}\right]=11 correspond au fait que le groupe symétrique S4 possède trois permutations de la forme

( * * )( * * ) — 2 cycles de longueur 2

et huit permutations de la forme

( * * * ) — 1 cycle de longueur 3 et 1 cycle de longueur 1.

La valeur absolue du nombre de Stirling de première espèce compte aussi le nombre de permutations de n objets ayant exactement k records. Cette identité entre records et cycles résulte de la correspondance fondamentale de Foata.

Nombres de Stirling de seconde espèce

Les Nombres de Stirling de seconde espèce \left\{\begin{matrix} n \\ k \end{matrix}\right\} comptent le nombre de relations d'équivalence ayant k classes d'équivalence définies sur un ensemble de n éléments, c'est-à-dire aussi le nombre de partitions en k sous-ensembles d'un ensemble de n objets. La somme

B_n=\sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\}

est le nème nombre de Bell. Si nous posons

(x)_n=x(x-1)(x-2)\cdots(x-n+1)

(en particulier, (x)0 = 1 car il s'agit d'un produit vide) pour la factorielle décroissante, nous pouvons caractériser les nombres de Stirling de seconde espèce par

\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\}(x)_k=x^n.

Table de valeurs

Voici quelques valeurs des nombres de Stirling de seconde espèce:

n \ k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1

Relation de récurrence

Ces nombres satisfont la relation de récurrence

\left\{\begin{matrix} n \\ k \end{matrix}\right\} = 
   \left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\} 
+k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}

avec

\left\{\begin{matrix} n \\ 1 \end{matrix}\right\}=1
\quad \mbox { et } \quad 
\left\{\begin{matrix} n \\ n \end{matrix}\right\} = 1
.

Identités simples

On a par exemple

\left\{\begin{matrix} n \\ n-1 \end{matrix}\right\} = 
{n \choose 2}

et

\left\{\begin{matrix} n \\ 2 \end{matrix}\right\} = 2^{n-1}-1

Formule explicite

Les nombres de Stirling de seconde espèce sont donnés par la formule explicite

\left\{\begin{matrix} n \\ k \end{matrix}\right\}
=\frac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j}{k \choose j} j^n.

Rapport avec la distribution de Poisson

Si X est une variable aléatoire suivant une distribution de Poisson avec une moyenne λ, alors son nème moment est

E(X^n)=\sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\}\lambda^k.

En particulier, le nème moment d'une distribution de Poisson de moyenne 1 est précisément le nombre de partitions d'un ensemble de taille n, qui est le nème nombre de Bell (formule de Dobinski).

Relation de réciprocité

Les nombres de Stirling de première et seconde espèce peuvent être considérés comme les inverses l'un de l'autre:

\sum_{n=0}^{\max\{j,k\}} 
\left[\begin{matrix} n \\ j \end{matrix}\right]
\left\{\begin{matrix} k \\ n \end{matrix}\right\}
= \delta_{jk}

et

\sum_{n=0}^{\max\{j,k\}} 
\left\{\begin{matrix} n \\ j \end{matrix}\right\}
\left[\begin{matrix} k \\ n \end{matrix}\right]
= \delta_{jk}

δjk est le symbole de Kronecker.

Voir aussi

Références

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Nombre de Stirling ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Nombre De Stirling de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Nombre de stirling — En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIIIe siècle. Il en existe deux sortes, nommés les nombres de Stirling de première …   Wikipédia en Français

  • Nombre de Stirling — En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIIIe siècle. Il en existe deux sortes, nommés les nombres de Stirling de première …   Wikipédia en Français

  • Stirling Albion Football Club — Stirling Albion F.C. Nombre completo Stirling Albion Football Club Apodo(s) Los Binos Fundación 1945 Estadio Estadio Forthbank ciudad, país …   Wikipedia Español

  • Nombre harmonique — En mathématiques, les nombres harmoniques d ordre sont donnés par . Le cas particulier est fréquemment écrit sans l exposant, sous la forme . Ces nombres apparaissent dans de nombreux problèmes d analyse combinatoire ; ainsi, on a …   Wikipédia en Français

  • STIRLING (J., 1692-1770) — STIRLING JAMES (1692 1770) Mathématicien anglais, né à Gardon (Stirling) et mort à Édimbourg, qui fit faire d’importants progrès à la théorie des séries. Renvoyé d’Oxford pour intelligence avec les jacobites, James Stirling vint, en 1715, étudier …   Encyclopédie Universelle

  • Nombre De Bell — Pour les articles homonymes, voir Bell. En mathématiques, les nombres de Bell, qui portent le nom de Eric Temple Bell, se rencontrent souvent en combinatoire. Ces nombres forment une suite d entiers qui commence ainsi : (suite …   Wikipédia en Français

  • Nombre de bell — Pour les articles homonymes, voir Bell. En mathématiques, les nombres de Bell, qui portent le nom de Eric Temple Bell, se rencontrent souvent en combinatoire. Ces nombres forment une suite d entiers qui commence ainsi : (suite …   Wikipédia en Français

  • Stirling Moss — Pour les articles homonymes, voir Moss. Stirling Moss Stirling Moss en 2008 Années d activité 1948 1962 …   Wikipédia en Français

  • Stirling Range — Chaîne de Stirling Chaîne de Stirling Image satellite du parc, les limites nettes de tous les côtés du parc montrent la passage brutal des terrains cultivés aux zones protégées. Géographie …   Wikipédia en Français

  • Nombre de Bernoulli — En mathématiques, les nombres de Bernoulli, notés (ou parfois , pour ne pas les confondre avec les polynômes de Bernoulli ou avec les nombres de Bell), constituent une suite de nombres rationnels. Les premiers nombres de Bernoulli sont donnés par …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”