2 • Exemples de groupes
55
- les autres ; elles sont obtenues en insérant le nouvel élément dans un des cycles. Or cela
peut se faire de r façons différentes dans un ,-cycle. Comme la somme des longueurs des
cycles est n, il y a n façons de prolonger une permutation des n premiers éléments. On a
donc:
s(n+ 1,k) = s(n,k- 1) +ns(n, k)
Cette formule convient pour k = I également, si l'on considère que s(n, 0) = O.
On peut initialiser cette relation en dénombrant les permutations circulaires :
n!
s(n, 1) = - = (n - l)! ;
n
on constate également que s(n, n) = 1. Vo ici la table des premières valeurs des s(n, k) que l'on
obtient:
I
0
0
0
0
0
0
0
0
0
0
0
2
3
I
0
0
0
0
6
Il
6
0
0
0
24
50
35
10
I
0
0
120
274
225
85
15
0
720
1764
16 24
735
175
21
5 040
13 068
13 132
6769
19 60
322
28
40 320
109 584
118 124
67284
22 449 4536
546
362 880 I 026 576 I 172 700 723 680 269 325 63 273 9450
2) Montrons maintenant la formule demandée, par récurrence sur n et posons
Alors:
Il
g11(X) = L s(n, k)X
k
k=I
811 + 1 (X) = E;;:: s(n + 1, k)X
k
= "'" s(n k - l )X
k
+ ll "'" s(n k)X
k
+ x
11 + 1
L.,k= J
'
L.,k=O
'
= "'11 - 1
s(n k)x
k + 1 + ng (X) + x
1 1+ 1
L.,k=O
,
1 1
= X(g 11 (X) - X") + ng,, (X) + X
11 + 1
= (X + n)g 11 (X)
En tenant compte de g 0 (X) = 1, on obtient bien :
Il
Ls(n,k)X
k
=X(X + 1) ... (X +n - 1)
k= I
0
0 0
0
0 0
0
0 0
0
0 0
0
0 0
0
0 0
0
0 0
I
0 0
36
0
870 45 I
www.bibliomath.com