Problemes de Mathematiques

Partitions dun ensemble fini, surjections, involutions

Enonce

Partitions dun ensemble fini, surjections, involutions

Soit E un ensemble fini non vide.

Pour tout entier k, on dit que {A1 , . . . , Ak } est une partition de E en k classes si :
k
[
Ai = E; i, Ai 6= ; i, j (avec i 6= j), Ai Aj =
i=1

Partie I
Dans cette partie, on suppose que Card(E) = n.
On note r(n) le nombre de partitions de E. On note r(0) = 1.
Pour tout k 1, on note r(n, k) le nombre de partitions de E en k classes.
1. Montrer que : k, n IN , k > n r(n, k) = 0. [ S ]
X n
2. Montrer que : n IN , r(n) = r(n, k). [ S ]
k=1
n
X
3. Montrer que : n IN, r(n + 1) = C kn r(k). [ S ]
k=0
4. Calculer r(n) pour n {1, 2, 3, 4, 5, 6}. [ S ]
5. Montrer que : n 5, r(n) 2n et n IN , r(n) nn . [ S ]
6. Dans cette question, on note Snk le nombre de surjections dun ensemble a n elements sur
un ensemble a k elements.
Montrer que : k, n IN , Snk = k!r(n, k). [ S ]

Partie II
On suppose que Card(E) = 2m, avec m 1.
On note am le nombre de partitions de E en m classes qui sont des paires.
1. Determiner a1 , a2 , a3 . Par convention, on pose a0 = 1. [ S ]
2. Montrer que : m IN , am = (2m 1)am1 . [ S ]
(2m)!
3. En deduire am = m . [ S ]
2 m!

Page 1 Jean-Michel Ferrard www.klubprepa.net EduKlub

c S.A.
Tous droits de lauteur des uvres reserves. Sauf autorisation, la reproduction ainsi que toute utilisation des uvres autre que la consultation
individuelle et privee sont interdites.
 Problemes de Mathematiques
Partitions dun ensemble fini, surjections, involutions
Enonce

Partie III
On suppose que Card(E) = n, avec n 1.
On note bn le nombre de partitions de E en classes qui sont des paires ou des singletons.
1. Determiner b1 , b2 , b3 , b4 . [ S ]
m
X
2. On suppose que n = 2m (m 1). Montrer que : b2m = C 2k
2m amk .
k=0
Indication : classer les partitions suivant le nombre de singletons quelles contiennent. [ S ]
3. Montrer que : n 3, bn = bn1 + (n 1)bn2 . [ S ]
4. Calculer bn , pour 1 n 10. [ S ]
5. Calculer le nombre dapplications involutives dans un ensemble a 10 elements. [ S ]

Page 2 Jean-Michel Ferrard www.klubprepa.net EduKlub

c S.A.
Tous droits de lauteur des uvres reserves. Sauf autorisation, la reproduction ainsi que toute utilisation des uvres autre que la consultation
individuelle et privee sont interdites.
 Problemes de Mathematiques
Partitions dun ensemble fini, surjections, involutions
Corrige

Corrige du probleme

PARTIE I
1. Supposons quil existe une partition en k classes {A1 , . . . , Ak }, donc r(n, k) > 0.
X k
Alors n = CardE = CardAj k (car pour tout k, CardAk 1).
j=1
Par consequent, si n < k, on a necessairement r(n, k) = 0. [ Q ]
2. Les differentes partitions de E peuvent etre regroupees en :
Celles qui ne comportent quune classe : il y en a r(n, 1) = 1.

Celles qui en comportent k : il y en a r(n, k).

Celles qui en comportent n : il y en a r(n, n) = 1.
n
X
On en deduit legalite : r(n) = r(n, k). [ Q ]
k=1
3. Soit E un ensemble de cardinal n + 1.
Soit P lune de ses r(n + 1) partitions. Fixons un element a de E.
Celui-ci appartient a une seule des parties de E qui composent la partition P.
Supposons que cette partie, notee A, soit de cardinal n + 1 k.
Il y a C nk
n manieres de construire A (on doit en effet choisir les nk elements restants
de A, parmi les n elements de E qui sont differents de a).
Une fois A construite, il reste a partitionner les n+1(n+1k) = k elements restants
dans E, ce qui peut se faire de r(k) manieres differentes.
On a donc C nkn r(k) = C kn r(k) manieres de construire une partition de E en supposant
que lelement a est dans une partie a n + 1 k elements.
Or cet indice k peut varier de de 0 a n.
n
X
On en deduit legalite : r(n + 1) = C kn r(k). [ Q ]
k=0
4. On trouve successivement
r(1) = C 00 r(0) = r(0) = 1.
r(2) = C 01 r(0) + C 11 r(1) = r(0) + r(1) = 2.
r(3) = C 02 r(0) + C 12 r(1) + C 22 r(2) = r(0) + 2r(1) + r(2) = 5.
r(4) = r(0) + 3r(1) + 3r(2) + r(3) = 15.
r(5) = r(0) + 4r(1) + 6r(2) + 4r(3) + r(4) = 52.
r(6) = r(0) + 5r(1) + 10r(2) + 10r(3) + 5r(4) + r(5) = 203.
[Q]

Page 3 Jean-Michel Ferrard www.klubprepa.net EduKlub

c S.A.
Tous droits de lauteur des uvres reserves. Sauf autorisation, la reproduction ainsi que toute utilisation des uvres autre que la consultation
individuelle et privee sont interdites.
 Problemes de Mathematiques
Partitions dun ensemble fini, surjections, involutions
Corrige

5. Inegalite r(n) 2n (par une recurrence double).

Puisque 25 = 32 et 26 = 64, on a bien r(5) 25 et r(6) 26 .
Soit n un entier donne, superieur ou egal a 6.
On suppose que les inegalites r(n) 2n et r(n 1) 2n1 sont vraies.
Xn
La formule r(n + 1) = C kn r(k) implique r(n + 1) C nn1 r(n 1) + C nn r(n).
k=0

Ainsi r(n + 1) nr(n 1) + r(n) n2n1 + 2n 2n+1 (car n 6 2).

On a donc montre (par une recurrence de pas deux) que n 5, r(n) 2n .
Inegalite r(n) nn (par recurrence forte).
Cette inegalite est verifiee si n = 1.
Soit n un entier positif fixe, et supposons r(k) k k pour tout k de {0, , n}.
Xn Xn Xn
k k k
Alors r(n + 1) = C n r(k) Cn k C kn nk .
k=0 k=0 k=0

Mais cette derniere expression nest autre que le developpement de (n + 1)n .

Ainsi, r(n + 1) (n + 1)n (n + 1)n+1 .
La propriete est demontree au rang n.
On a donc prouve, par recurrence, linegalite r(n) nn , pour tout n de IN.
[Q]
6. Soit E un ensemble de cardinal n et F = {y1 , y2 , . . . , yk } de cardinal k.
Il y a Snk surjections de E sur F . Pour definir lune delles, il faut :
Regrouper les elements de E qui vont avoir la meme image.
Cela revient a partitionner E en k classes.
On sait quil y a r(n, k) manieres deffectuer une telle partition.
Supposons quune telle partition soit choisie.
Il faut encore associer bijectivement les k classes aux k elements de F .
Cela peut se faire de k! manieres differentes.

Ce denombrement prouve que Snk = k!r(n, k). [ Q ]

PARTIE II
1. Si E = {a, b}, il ny a quune partition qui convienne.
Si E = {a, b, c, d}, il y a trois partitions possibles, qui sont :
{{a, b}, {c, d}}, {{a, c}, {b, d}}, et {{a, d}, {b, c}}. Donc a2 = 3.

Page 4 Jean-Michel Ferrard www.klubprepa.net EduKlub

c S.A.
Tous droits de lauteur des uvres reserves. Sauf autorisation, la reproduction ainsi que toute utilisation des uvres autre que la consultation
individuelle et privee sont interdites.
 Problemes de Mathematiques
Partitions dun ensemble fini, surjections, involutions
Corrige

Si E = {a, b, c, d, e, f }, il y a 5 manieres dapparier f .

On doit ensuite partitionner les quatre elements restants (a2 = 3 possibilites).
Donc a3 = 5a2 = 15.
[Q]
2. Soit E = {x1 , x2 , . . . , x2m1 , x2m }, avec m 1.
Pour creer une partition de E en paires, il faut :
Apparier x1 avec lun quelconque des 2m 1 autres elements.
Partitionner en paires lensemble des 2(m 1) elements restants.
Pour cela, il y a am1 possibilites.
Ce denombrement prouve que am = (2m 1)am1 (vrai si m = 1 car a0 = 1.) [ Q ]
3. On en deduit, pour tout m de IN :
(2m)! (2m)!
am = (2m 1)(2m 3) 3 1 = = m
(2m)(2m 2) 4 2 2 m!
[Q]

PARTIE III
1. Si E = {a}, il ny a quune solution possible. Donc b1 = 1.
Si E = {a, b}, on partionne en les deux singletons, ou en lunique paire. Donc b2 = 2.
Si E = {a, b, c}, la partition contient trois singletons (1 possibilite), ou bien un singleton
et la paire restante (3 possibilites). Donc b3 = 4.
Si E = {a, b, c}, on classe suivant le nombre de singletons qui apparaissent :
Quatre singletons : 1 possibilite.
Deux singletons et la paire restante : C 24 = 6 possibilites.
Aucun singleton (donc deux paires) : a2 = 3 possibilites.
On en deduit b4 = 10.
[Q]
2. On pose E = {x1 , x2 , , x2m1 , x2m }.
On considere une partition de E formee de paires ou de singletons. Il y en a b2m .
Le nombre de singletons qui figurent dans cette partition est evidemment pair.
Soit 2k ce nombre : k est compris entre 0 et m.
Il y a C 2k
2m manieres de choisir ces 2k singletons parmi les 2m elements de E.
Puis il y a amk manieres de partitionner en paires les 2(m k) elements restants.
m
X
Dans ce calcul, on fait varier k de 0 a m : on obtient b2m = C 2k2m amk . [ Q ]
k=0

Page 5 Jean-Michel Ferrard www.klubprepa.net EduKlub

c S.A.
Tous droits de lauteur des uvres reserves. Sauf autorisation, la reproduction ainsi que toute utilisation des uvres autre que la consultation
individuelle et privee sont interdites.
 Problemes de Mathematiques
Partitions dun ensemble fini, surjections, involutions
Corrige

3. On pose E = {x1 , x2 , , xn }.
Considerons lune des bn partitions de E en paires ou singletons.
De deux choses lune :
Ou bien {x1 } est lun des singletons de la partition.
Il faut alors partitionner les n 1 elements restants, en paires ou singletons.
Cela peut se faire de bn1 manieres.
Ou bien x1 est un des deux elements dune paire de la partition.
Il y a n 1 manieres de choisir le deuxieme element de cette paire.
Il reste a partitionner les n 2 elements restants, en paires ou singletons.
Cela peut se faire de bn2 manieres.
Ce denombrement prouve que, pour tout n 3, bn = bn1 + (n 1)bn2 . [ Q ]
4. On trouve successivement :
b1 = 1, b2 = 2 b3 = b2 + 2b1 = 4 b4 = b3 + 3b2 = 10
b5 = b4 + 4b3 = 26 b6 = b5 + 5b4 = 76 b7 = b6 + 6b5 = 232 [Q]
b8 = b7 + 7b6 = 764 b9 = b8 + 8b7 = 2620 b10 = b9 + 9b8 = 9496
5. Soit E un ensemble ayant 10 elements.
Soit f une application involutive de E.
Soit a un element de E. De deux choses lune :
Ou bien f (a) = a (autrement dit a est invariant par f .)
Ou bien f (a) = b 6= a, mais dans ce cas f (b) = a car f est involutive.

On voit quon peut partionner E en paires ou singletons :

Les singletons sont les ensembles {x} pour tous les elements invariants par f .
Les paires {x, y} groupent les elements distincts avec f (x) = y et f (y) = x.

Reciproquement donnons-nous une partition de E en paires et singletons.

Elle definit de maniere unique une application injective f de E dans E :
Pour chaque singleton {x}, on pose f (x) = x.
Pour chaque paire {x, y}, on pose f (x) = y et f (y) = x.

Le nombre dapplications involutives de E est donc egal au nombre de partitions de E en

paires et singletons, cest-a-dire b10 = 9496. [ Q ]

Page 6 Jean-Michel Ferrard www.klubprepa.net EduKlub

c S.A.
Tous droits de lauteur des uvres reserves. Sauf autorisation, la reproduction ainsi que toute utilisation des uvres autre que la consultation
individuelle et privee sont interdites.