Cours - Ensembles Finis Et Denombrement [PDF]

Zitiervorschau

c Christophe Bertault - MPSI

Ensembles finis et dénombrement Définition (Ensemble fini/infini) Soit E un ensemble. On dit que E est fini s’il est vide ou si, pour un certain n ∈ N× , il existe une bijection de l’ensemble J1, nK sur E ; on dit sinon que E est infini.

   Explication Ce chapitre est intégralement dirigé par une idée : l’idée selon laquelle une bijection de E sur F établit une correspondance parfaite entre les éléments de E et les éléments de F ; c’est la manière qu’ont trouvé les mathématiciens pour décrire la taille, le nombre d’éléments des ensembles — appelé cardinal. Cette théorie nous permettrait de parler aussi des ensembles infinis si nous le voulions, mais cela n’est pas au programme — et c’est plus compliqué.

1

Cardinal d’un ensemble fini

Définition (Cardinal d’un ensemble fini) Soit E un ensemble fini non vide. On appelle cardinal de E ou nombre d’éléments de E tout entier n ∈ N× pour lequel il existe une bijection de J1, nK sur E. On convient que le vide est de cardinal 0, ce qu’on note :

Théorème

card(∅) = 0.

(Unicité du cardinal)

(i) Soient m, n ∈ N. Il existe une bijection de J1, mK sur J1, nK si et seulement si m = n. (ii) Soit E un ensemble fini. Il existe un et un seul cardinal de E, noté card E (ou #E ou |E|).

Démonstration (i) Résultat admis. (ii) Soient m et n deux cardinaux de E, i.e. deux entiers naturels non nuls pour lesquels existent une bijection f : J1, mK −→ E et une bijection g : J1, nK −→ E. Alors g −1 ◦ f est une bijection de J1, mK sur J1, nK, et aussitôt m = n via l’assertion (i).  Exemple

Soient m, n ∈ Z tels que m 6 n. Alors Jm, nK est fini et card Jm, nK = n − m + 1. 

En effet 

cation

J1, n − m + 1K −→ Jm, nK . Cette application est bijective car l’applik 7−→ k + m − 1 J1, n − m + 1K en est la réciproque. Cela montre bien le résultat voulu. k−m+1

Soit f l’application Jm, nK k

−→ 7−→

Théorème Soient E et F deux ensembles. On suppose que E est fini et qu’il existe une bijection de E sur F . Alors F est fini et card E = card F .

Démonstration Si E est vide, le résultat est immédiat car F est alors vide lui aussi. Supposons donc que E n’est pas vide, et puisque E est fini, donnons-nous une bijection g de J1, card EK sur E. Soit alors f une bijection de E sur F , conformément à l’hypothèse du théorème. Alors f ◦ g est une bijection de J1, card EK sur F , donc en effet F est fini, et card F = card E par unicité du cardinal. 

Théorème (Parties d’un ensemble fini) Soient E un ensemble fini et A une partie de E. Alors A est finie et card A 6 card E. De plus A = E si et seulement si card A = card E.

   En pratique Pour montrer que deux parties finies A et B d’un ensemble E sont égales, au lieu de montrer que A ⊆ B et que B ⊆ A, on peut se contenter de montrer, grâce au théorème précédent, que A ⊆ B et que card A = card B. Cette remarque est très utile dans certains contextes.

1

c Christophe Bertault - MPSI

Démonstration

Récurrence sur n = card E.

• Initialisation : Pour n = 0, E est vide, et donc A aussi. Ainsi A = E et il n’y a rien à montrer. • Hérédité : Soit n ∈ N. On suppose que pour tout ensemble fini E de cardinal n et toute partie A de E, A est finie telle que card A 6 card E, et que de plus A = E si et seulement si card A = card E. Donnons-nous alors E un ensemble fini de cardinal (n + 1) et A une partie de E. Si A = E, tout va bien. Supposons donc A 6= E. Cette preuve étant abstraite, donnons-en rapidement l’idée. Partant d’une bijection f de J1, n + 1K sur E, nous allons restreindre celle-ci à l’ensemble J1, nK. Nous récupérerons ainsi une bijection de J1, nK sur n o E 0 = E r f (n + 1) , ce qui montrera en particulier que card E 0 = n. Nous espérons ainsi pouvoir appliquer

l’hypothèse de récurrence à l’ensemble E 0 , mais pour que cela nous parle de A, il faut être sûr d’avoir A ⊆ E 0 . Or cela n’est vrai que si f (n + 1) ∈ / A. La question pertinente est donc la suivante : peut-on toujours choisir f de façon à avoir f (n + 1) ∈ / A? 1) Montrons qu’il existe une bijection f de J1, n + 1K sur E telle que f (n + 1) ∈ / A. Ce qui est vrai en tout cas, c’est qu’il existe une bijection f de J1, n + 1K sur E, puisque card(E) = n + 1. Si f (n + 1) ∈ / A, nous sommes heureux. Supposons au contraire que f (n + 1) ∈ A. Comme A 6= E, il existe un élément ω ∈ E extérieur à A. Définissons alors l’application f˜ : J1, n + 1K −→ E en posant : ∀k ∈ J1, n + 1K,

f˜(k) =

8 < f (k)

si f (k) 6= ω et k 6= n + 1 ; si k = n + 1 ; si f (k) = ω.

ω : f (n + 1)

En somme, f˜ et f sont identiques à ceci près qu’on a échangé leurs valeurs ω ∈ / A et f (n + 1) ∈ A. Vous montrerez seuls, proprement, que f˜ est bijective de J1, n + 1K sur E. Comme f˜(n + 1) = ω ∈ / A, on a montré ce qu’on voulait montrer. 2) Conformément au point précédent, nous n pouvons nous o donner f une bijection de J1, n + 1K sur 0 E telle que f (n + 1) ∈ / A. Posons alors E = E r f (n + 1) . Comme voulu, A est une partie de E 0 car f (n + 1) ∈ / A. Nous allons montrer que E 0 est de cardinal n pour pouvoir lui appliquer notre hypothèse de récurrence. Or la restriction de f à J1, nK induit une bijection de J1, nK sur E 0 , par construction. Cela montre que E 0 est fini de cardinal n. Par hypothèse de récurrence, A est donc un ensemble fini et de plus on a les inégalités card A 6 card E 0 = n < n + 1 = card E. Au passage, nous venons de montrer par contraposition l’implication « card A = card E =⇒ A = E » grâce à l’inégalité stricte précédente. 

Théorème

(Injectivité, surjectivité et ensembles finis) Soient E et F deux ensembles et f : E −→ F une application.

(i) Si f est injective et si F est fini, alors E aussi est fini et card E 6 card F . Si de plus card E = card F , f est en fait bijective de E sur F . (ii) Si f est surjective et si E est fini, alors F aussi est fini et card F 6 card E. Si de plus card E = card F , f est en fait bijective de E sur F . (iii) Si E et F sont finis de même cardinal, on a l’équivalence suivante : f est bijective

⇐⇒

f est injective

f est surjective.

⇐⇒

   Explication

• Tâchons de comprendre intuitivement l’assertion (i). Dire que f est injective, c’est dire que pour tous x, x0 ∈ E, si x 6= x0 alors f (x) 6= f (x0 ). En français, ceci signifie que deux points distincts dans E sont envoyés par f sur deux points distincts de F . Ainsi f transporte les points de E dans F sans en faire disparaître aucun, sans qu’aucun se retrouve au même endroit qu’aucun autre. Dit autrement, ceci veut dire que f crée une copie de E dans F . Or une telle copie n’est possible que si F est « plus gros » que E, que s’il y a dans F assez de place pour accueillir une copie de E. Voilà pourquoi card E 6 card F .

F f injective

E

f (E)

b b

b b

b

b

• Faites l’effort de comprendre intuitivement l’assertion (ii) tout comme nous venons de comprendre l’assertion (i). • L’assertion (iii) vous rappelle certainement un théorème du chapitre « Espaces vectoriels de dimension finie » que nous avons beaucoup aimé car il était très utile et facile à manipuler. De même qu’on avait alors impérativement besoin de la condition « dim E = dim F », on a dans le cas présent besoin de la condition « card E = card F ».

2

c Christophe Bertault - MPSI

Démonstration (i) Supposons f injective de E sur F . Comme f (E) est une partie de F , nous savons que f (E) est fini et que card f (E) 6 card F . Or f est bijective de E sur son image f (E). Via un théorème précédent, la finitude de f (E) implique donc la finitude de E et de plus card f (E) = card E. Finalement, nous avons montré que card E 6 card F comme voulu. (ii) Supposons f surjective de E sur F et donnons-nous ϕ une bijection de J1, card EK sur E. Alors f ◦ ϕ est surjective de J1, card EK sur F par composition.
−1

Posons, pour tout y ∈ F , Ay = f ◦ ϕ




J1, card EK =

n

o

k ∈ J1, card EK/

f ◦ ϕ(k) = y . Cet Ay

est une partie de N, il possède donc un plus petit élément µ(y). Nous disposons ainsi
d’une application µ : F −→ J1, card EK. Par ailleurs, pour tout y ∈ F , µ(y) ∈ Ay , donc f ◦ ϕ µ(y) = y ; on a donc f ◦ ϕ ◦ µ = IdF .





Montrons que µ est injective. Soient y, y 0 ∈ F tels que µ(y) = µ(y 0 ). Alors y = f ◦ϕ µ(y) = f ◦ϕ µ(y 0 ) = y 0 , et voilà le travail. Finalement, µ est injective de F dans J1, card EK. Le premier point montre aussitôt que F est fini et que card F 6 card E, comme voulu. (iii) Supposons E et F finis de même cardinal. Alors bien sûr, si f est bijective, f est injective et surjective. • Supposons f injective. Alors nous avons vu dans la preuve de (i) que card f (E) = card E. Du coup, card f (E) = card E = card F . Or f (E) est une partie de F , donc f (E) = F , et enfin f est surjective, donc également bijective. • Supposons f surjective et reprenons l’application µ utilisée en (ii). Cette application µ est injective de F dans J1, card EK. Puisque E et F sont supposés finis de même cardinal, le point précédent dans (iii) montre que µ est mieux qu’injective, elle est en fait bijective. L’égalité f ◦ ϕ ◦ µ = IdF peut donc s’écrire f = µ−1 ◦ ϕ−1 et ainsi f est bijective. 

Théorème

(Parties finies de N) Soit A une partie de N. A est finie si et seulement si A est majorée.

Dans ce cas, si de plus A 6= ∅, il existe une et une seule bijection (strictement) croissante de J1, card AK sur A.

   Explication Mais à quoi ce théorèmenpeut-il bien servir ? Quand on travaille avec une partie finie A de N, on a o naturellement envie d’écrire A sous la forme A = a1 , a2 , . . . , an où n = card A et où a1 < a2 < . . . < an . Bref, on a bien envie de ranger les éléments de A dans l’ordre croissant. Maisest-ce au moins possible ? Eh bien oui, c’est ce que nous dit le J1, nK −→ A , qui permet en effet un classement croissant présent théorème. La bijection qu’il décrit est ici l’application i 7−→ ai des éléments de A.

Démonstration • Si A est finie, de deux choses l’une : ou bien A est vide, donc évidemment majorée par tout entier ; ou bien A est non vide, et possède donc un plus grand élément, donc est majorée. Dans les deux cas, A est majorée. Réciproquement, si A est majorée, disons par M ∈ N, alors A ⊆ J0, M K. Or J0, M K est fini, donc A également. • Supposons à présent A finie non vide et notons n = card A. Nous voulons montrer qu’il existe une et une seule bijection strictement croissante ϕ de J1, card AK = J1, nK sur A. 1) Analyse : Supposons l’existence de ϕ. Soit k ∈ J1, nK. Comme ϕ est strictement croissante, nous disposons de la chaîne d’inégalités suivante : ϕ(1) < ϕ(2) < . . . < ϕ(k − 1) < ϕ(k) < ϕ(k + 1) < . . . < ϕ(n). Comme ϕ est bijective d’image A, il faut bien remarquer que tous les éléments de A figurent dans cette chaîne d’inégalités. Il apparaît alors que ϕ(k) est le plus petit élément de A privé des valeurs n o ϕ(1), ϕ(2), . . . , ϕ(k − 1). Bref : ϕ(k) = min A r ϕ(1), ϕ(2), . . . , ϕ(k − 1) . Fin de l’analyse. |

{z

}

∅ par convention si k=1

2) Synthèse : Définissons ϕ de façon récursive en posant, pour tout k ∈ J1, nK : n

o

ϕ(k) = min A r ϕ(1), ϕ(2), . . . , ϕ(k − 1) . |

{z

∅ par convention si k=1

(initialisation)

3

}

c Christophe Bertault - MPSI

Montrons que ϕ est strictement croissante. Soit k ∈ J1, n − 1K. Partons de l’inclusion : n

o

n

o

A r ϕ(1), ϕ(2), . . . , ϕ(k) ⊆ A r ϕ(1), ϕ(2), . . . , ϕ(k − 1) , n

o

et passons-la aux « min » : on obtient ϕ(k) 6 ϕ(k + 1). Et comme ϕ(k) ∈ / A r ϕ(1), ϕ(2), . . . , ϕ(k) , il est impossible d’avoir ϕ(k) = ϕ(k + 1). On a donc l’inégalité stricte désirée :

ϕ(k) < ϕ(k + 1).

Pour conclure, remarquons que ϕ est une application strictement croissante, donc injective de J1, nK dans A, et que card J1, nK = card A. Un théorème vu précédemment affirme enfin que ϕ est bijective comme nous l’attendions. 

Dénombrement

2 2.1

Réunion, intersection et différence d’ensembles finis

Théorème (Cardinal de la réunion/intersection/différence de deux ensembles finis) Soient A et B deux ensembles finis.

(i) Alors A ∪ B est fini et card A ∪ B = card
A + card B − card A ∩ B . En particulier, si A et B sont disjoints, card A ∪ B = card A + card B.





(ii) card A r B = card A − card A ∩ B .
En particulier, si B est une partie de A, card B c = card A r B = card A − card B.

   Explication On peut dessiner quelques patates pour bien visualiser ce théorème. Dans le cas de la réunion, pour trouver le nombre d’éléments dans A ∪ B, il faut compter les éléments de A et ceux de B en les additionnant, mais en faisant cela, on compte deux fois les éléments qui sont à la fois dans A et B, i.e. les éléments de A ∩ B ; c’est pourquoi il convient de les retrancher.

Démonstration

A A∩B B

Posons m = card A et n = card B.

• Commençons par démontrer l’assertion (i) dans le cas où A et B sont disjoints. Le résultat étant évident si A ou B est vide, nous nous donc plaçons dans le cas contraire. Soient α (resp. β) une bijection de J1, mK sur A (resp. de J1, nK sur B). Nous définissons l’application γ de A ∪ B dans J1, m + nK en posant : 

∀x ∈ A ∪ B,

γ(x) =

α−1 (x) m + β −1 (x)

si x ∈ A . si x ∈ B

Bien sûr, une application est ainsi proprement définie car A et B sont supposés disjoints — x appartient à A ou à B, pas aux deux. Il se trouve alors que γ est une bijection de A ∪ B sur J1, m + nK comme nous allons le prouver à présent. Injectivité de γ : Soient x, y ∈ A ∪ B tels que γ(x) = γ(y). Plusieurs possibilités s’offrent à nous. 1) Si x et y sont dans A, alors α−1 (x) = γ(x) = γ(y) = α−1 (y), et comme α−1 est injective, x = y. 2) Si x et y sont dans B, alors β −1 (x) = γ(x) = γ(y) = β −1 (y), et comme β −1 est injective, x = y. 3) Enfin, si x est dans A et y dans B — idem si c’est l’inverse — alors γ(x) = α−1 (x) ∈ J1, mK et γ(y) = m + β −1 (y) ∈ Jm + 1, m + nK. Nous avons donc : γ(x) = γ(y) ∈ J1, mK ∩ Jm + 1, m + nK = ∅.

La situation 3) est donc contradictoire.

Surjectivité de γ : Soit i ∈ J1, card A + card BK. 1) Si i ∈ J1, mK, alors il existe a ∈ A tel que α−1 (a) = i. On a donc γ(a) = α−1 (a) = i. 2) Sinon i ∈ Jm + 1, m + nK, donc i − m ∈ J1, nK. Il existe alors b ∈ B tel que β −1 (b) = i − m. On a donc γ(b) = m + β −1 (b) = i. Au final, γ est une bijection de A ∪ B sur J1, m + nK, donc A ∪ B est un ensemble fini de cardinal m + n. On a finalement obtenu l’égalité : card(A ∪ B) = card A + card B. • Démontrons l’assertion que parties de A, A r B et A ∩ B sont des ensembles finis. Mais par
(ii). En tant
ailleurs A = hA r B ∪ A ∩ B ,ioù A r B et A ∩ B sont disjoints. Le premier point affirme donc que


card A = card A r B ∪ A ∩ B










= card A r B + card A ∩ B . C’est justement ce que nous voulions.

4

c Christophe Bertault - MPSI

• Finissons-en avec le cas général
de l’assertion (i). En tant que partie de A, A r B est un ensemble fini. Mais par ailleurs A ∪ B = A r
B ∪ B, où A r
B et B sont disjoints. Le premier point affirme donc que A ∪ B est fini et que card A
∪ B = card A r B + card B. Mais
nous pouvons aussi utiliser l’assertion (ii), et  finalement card A ∪ B = card A + card B − card A ∩ B comme voulu. Remarque

Si A1 , A2 , . . . , An sont des ensembles finis ! deux à deux disjoints (n ∈ N× ), on peut généraliser la formule du n

théorème précédent de la façon suivante :

[

card

=

Ai

X

2.2

card Ai .

i=1

16i6n

Produit cartésien d’ensembles finis

Théorème (Cardinal du produit cartésien de deux ensembles finis) Soient E et F deux ensembles finis. Alors E × F est fini et :
card E × F = card E × card F .

Démonstration Se donner deux bijections conformes à la définition de la finitude de E et F , ce n’est rien de plus que numéroter les éléments de E et Nous n o F pour les distinguer. n o pouvons ainsi énumérer les éléments de E et F en posant : E = e1 , e2 , . . . , em et F = f1 , f2 , . . . , fn , si m = card E et n = card F . Alors par n

définition :

o

E × F = (ei , fj )

16i6m, 16j6n

. n





o

F −→ Ai étant f 7−→ (ei , f ) clairement bijective, nous pouvons affirmer que Ai est un ensemble fini de même cardinal que F . Il se trouve par ailleurs que la réunion des Ai (1 6 i 6 m) est E × F tout entier, et que les Ai sont deux à deux disjoints. En vertu de la remarque du paragraphe précédent, l’ensemble E × F est donc fini et on a : Pour tout i ∈ J1, mK, posons à présent Ai = ei × F = (ei , fj )




card E × F = card

m [ i=1

!

Ai

=

m X

card Ai =

i=1

m X

16j6n

; l’application

card F = m card F = card E × card F.



i=1

Remarque Si E1 , E2 , . . . , En sont des ensembles finis (n ∈ N× ), on peut généraliser la formule du théorème précédent de la
façon suivante : card E1 × E2 × . . . × En = card E1 × card E2 × . . . × card En . En particulier, si E est un ensemble fini et si k ∈ N× :




card E k = card E


k

.

   Explication Ce résultat est souvent utilisé en théorie des probabilités ou lorsqu’on fait du dénombrement. On introduit alors souvent le vocabulaire suivant : si E est un ensemble fini et si p ∈ N× , on appelle p-liste de E (p-uplet de E) toute famille de p éléments de E, c’est-à-dire tout élément de E p . On rappelle ci-après deux propriétés fondamentales des listes.

• Dans une liste, l’ordre des éléments compte. Une liste n’est jamais qu’une famille ; or quand on travaille n l’ordre compte o avec les familles. Ainsi, (1, 2, 3) et (2, 1, 3) sont deux 3-listes distinctes de l’ensemble 1, 2, 3, 4, 5 . n

• Dans une liste, un même élément peut apparaître plusieurs fois. Ainsi (1, 1, 2, 3) est une 4-liste de l’ensemble

o

1, 2, 3 .

Les listes servent souvent à modéliser des tirages successifs avec remise dans une urne, un jeu de cartes. . . Le théorème précédent montre en particulier que tout ensemble fini de cardinal n possède np p-listes distinctes. Ainsi le nombre de façons de tirer 5 cartes successivement avec remise dans un jeu de 52 cartes est 525 .

2.3

Applications entre ensembles finis

Théorème (Nombre d’applications entre deux ensembles finis) Soient E et F deux ensembles finis.

card E Alors l’ensemble F E des applications de E dans F est fini et : card F E = card F .

Démonstration Soient n = card E et ϕ une bijection de J1, nK sur E. L’idée de la preuve est la suivante : nous savons que F n est l’ensemble des applications de J1, nK dans F et que F E est l’ensemble des applications de E dans F ; or il y a, via ϕ, le même nombre d’éléments dans E et dans J1, nK ; par conséquent, F n et F E ont le
n
card E . même nombre d’éléments, i.e. card F E = card F n = card F = card F

5

c Christophe Bertault - MPSI

Pour être précis, considérons les deux applications suivantes : 

S:

FE f

−→ 7−→

Alors S ◦ T = IdF n et T ◦ S = IdF E . En effet : ∀(fi )16i6n ∈ F n , ∀f ∈ F E ,

et :



Fn
f ◦ ϕ(i) 16i6n 

et



T :



Fn (fi )16i6n 

FE
. x 7−→ fϕ−1 (x)

−→ 7−→





S ◦ T (fi )16i6n = S x 7−→ fϕ−1 (x) = fϕ−1 (ϕ(i)) 

f ◦ ϕ(i)

T ◦ S(f ) = T




16i6n



= x 7−→ f ◦ ϕ ϕ−1 (x)

16i6n




= (fi )16i6n


= x 7−→ f (x) = f.

Nous pouvons donc affirmer que S et T sont bijectives, réciproques l’une de l’autre. En particulier, comme voulu,
n
card E F E est fini et card F E = card F n = card F = card F .  La définition suivante est un rappel. Nous avons notamment évoqué ces notions dans les chapitres « Groupes, anneaux, corps » et « Déterminant ». Définition

(Permutation, groupe des permutations) Soit E un ensemble fini non vide.

• Une bijection de E sur E est souvent appelé une permutation de E. • L’ensemble des permutations de E est appelé le groupe symétrique de E et noté SE (ou parfois SE ). Dans le cas où E = J1, nK pour un certain n ∈ N× , le groupe symétrique de E est généralement noté Sn (ou parfois Sn ).

Théorème (Nombre de permutations
d’un ensemble fini) Soient E un ensemble fini non vide. Alors SE est fini et : card SE = card E !

   Explication On peut expliquer ce résultat simplement en agitant les mains. La preuve rigoureuse est cependant plus compliquée. Ce qu’il faut commencer par comprendre, c’est qu’une permutation de E — qui est fini — n’est en réalité jamais qu’une injection de E dans E. En effet, injectivité et bijectivité coïncident quand les ensembles de départ et d’arrivée sont de même cardinal (fini). Du coup, construire une permutation de E revient à construire une injection de E dans E. Or comment construit-on une injection de E dans E ? Notons x1 , x2 , . . . , xn les éléments distincts de E, avec n = card E. Pour construire une injection f de E dans E, on commence par associer à x1 un élément f (x1 ) de E ; le choix de f (x1 ) est indifférent — n possibilités. Ensuite on associe à x2 un certain f (x2 ) qu’il faut choisir différent de f (x1 ) si on veut l’injectivité de f — (n − 1) possibilités. Vient ensuite un f (x3 ) différent de f (x1 ) et f (x2 ), etc. A la fin, on n’a plus qu’un seul choix pour f (xn ) car tous les éléments de E ont été appelés une fois, sauf un. Combien avons-nous eu de possibilités de construction de f ? Facile :

n × (n − 1) × (n − 2) × . . . × 2 × 1 = n!

Démonstration

Par récurrence sur card E. Soyez prévenus : cette preuve est propre mais peu digeste.

• Initialisation : Si card E = 1, alors il existe une et une seule bijection de E sur E : elle envoie l’unique
élément de E sur lui-même. Ainsi SE est fini et comme voulu : card SE = 1 = 1! = card E ! • Hérédité : Soit n ∈ N× . Supposons que pour tout ensemble A de cardinal n, SA est fini de cardinal n! Soit alors E un ensemble fini de cardinal (n + 1). Fixonsoune fois pour toutes un élément e ∈ E. Pour tout n x ∈ E, nous noterons Fx l’ensemble f ∈ SE / f (e) = x . Il est assez clair que SE est la réunion disjointe des Fx , x parcourant E. Nous allons montrer que Fx est fini pour tout X x ∈ E et calculer son cardinal. Nous pourrons alors conclure grâce à la formule suivante : card SE = card Fx . x∈E

Fixons donc x ∈ E ainsi que fx ∈ Fx . Alors pour tout f ∈ Fx , on a : fx−1 ◦ f (e) = fx−1 (x) = e. −1 −1 En d’autres termes, fx ◦ f fixe e. Comme par
ailleurs fx ◦ f est une permutation de E, sa restriction fx−1 ◦ f est une permutation de E r e . Nous pouvons donc nous pencher un peu sur l’application (

Tx :

Er{e}

Fx f

−→ 7−→

SEr{e}
fx−1 ◦ f

. Er{e}

1) Tx est injective. En effet, soient f, f¯ ∈ Fx telles que Tx (f ) = Tx (f¯). Pour montrer que f = f¯, nous devons montrer que f (t) = f¯(t) pour tout t ∈ E. ¯ ¯ Ce qui est clair, c’est  que f (e) = f (e) = x puisque f, f ∈ F
x .

Soit alors t ∈ E r e . Nous savons que Tx (f )(t) = Tx f¯ (t), i.e. que fx−1 f (t) = fx−1 f¯(t) . Or fx est une permutation de E, donc est injective, et donc f (t) = f¯(t) comme voulu.

6

c Christophe Bertault - MPSI

2) Tx est surjective. Eneffet, soit ϕ ∈ SEr{e} . Nous devons construire f ∈ Fx telle que Tx (f ) = ϕ. x
si t = e  . Posons : ∀t ∈ E, f (t) = fx ϕ(t) si t ∈ E r e Ainsi définie, f est une application de E dans E. Vous montrerez seuls que f est bijective : pour cela, il vous suffira de montrer que f est injective, puisque f ∈ Fx .  E est fini. Finalement,
Enfin il est clair que Tx (f ) = ϕ car : ∀t ∈ E r e , Tx (f )(t) = fx−1 ◦ f (t) = fx−1 ◦ fx ϕ(t) = ϕ(t). 

Finalement, nous avons prouvé que Tx est une bijection de Fx sur SEr{e} . Or E r e est un ensemble de cardinal n, donc via notre pouvons affirmer que Fx est fini de cardinal n! Xhypothèse de Xrécurrence, nous
Enfin ( !) : card SE = card Fx = n! = card E × n! = (n + 1) × n! = (n + 1)!  x∈E

2.4

x∈E

Parties d’un ensemble fini

Définition (Combinaison d’un ensemble fini) Soient E un ensemble fini et p ∈ N. On appelle p-combinaison de E (ou combinaison de p éléments de E) toute partie de E de cardinal p.

   Explication

• De toute évidence, il n’existe de p-combinaison d’un ensemble à n éléments que si p 6 n. • Dans une combinaison, qui est un ensemble et non une famille, les éléments sont donnés sans ordre aucun. Quand on décide de numéroter les éléments d’une combinaison, le choix de la numérotation est totalement arbitraire, la combinaison en tant que telle n’a pas un premier élément, un deuxième élément, etc.

Théorème Il existe

(Nombre de combinaison d’un ensemble fini) Soient E un ensemble fini de cardinal n ∈ N et p ∈ N, p 6 n. ! n n! = p-combinaisons distinctes de E. p p!(n − p)!

Démonstration

Pour la clarté de l’exposition, nous ferons ici une preuve « avec les mains ».

• On appelle p-arrangement de E toute p-liste de E dont les éléments sont distincts. Une p-liste n’étant au fond qu’une famille de p éléments de E, c’est-à-dire qu’une application de J1, pK dans E, un p-arrangement de E n’est donc jamais qu’une application injective de J1, pK dans E. Comptons le nombre des p-arrangements de E. Construire un p-arrangement de E, c’est tout d’abord remplir la première position du p-arrangement en y mettant un élément quelconque x1 de E ; ceci peut se faire de n façons. C’est ensuite placer un monsieur x2 en deuxième position, lequel ne peut être égal à x1 par définition ème d’un p-arrangement — (n − 1) élément, à
possibilités. On continue ainsi jusqu’à n’avoir plus qu’au p choisir parmi les n − (p − 1) éléments de E non encore sélectionnés. Au final, nous avons pu construire n! p-arrangements distincts. Ce nombre est généralement noté Apn . n × (n − 1) × . . . × (n − p + 1) = (n − p)! Apn . p! Or nous remarquons qu’un p-arrangement de E n’est rien d’autre qu’une permutation d’une p-combinaison de E. Ainsi, se donner un p-arrangement de E, c’est : 1) choisir une p-combinaison C quelconque de E — Kpn choix possibles — puis 2) ayant fixé une telle p-combinaison C, qui n’est rien de plus qu’une partie de E à p éléments, choisir une façon d’ordonner les éléments de C, i.e. choisir une permutation quelconque de C — p! choix possibles. Tout ceci montre que le nombre Apn des p-arrangements distincts de E satisfait la formule Apn = Kpn × p! C’est bien ce que nous voulions. 

• Notons alors Kpn le nombre des p-combinaisons distinctes de E. Nous voulons montrer que Kpn =

   Explication

• Les combinaisons servent souvent, en théorie des probabilités par exemple, à modéliser des tirages simultanés dans ! une 52 urne, un jeu de cartes. . . Ainsi, le nombre de façons de tirer 5 cartes simultanément dans un jeu de 52 cartes est . 5 • En dénombrant les p-arrangements d’un ensemble à n éléments, notez bien que nous avons dénombré les applications injectives d’un ensemble d’un ensemble fini de cardinal p dans un ensemble fini de cardinal n. La démonstration de ce résultat constitue un exercice classique.

7

c Christophe Bertault - MPSI

Théorème (Nombre de parties d’un ensemble fini) Soit E est un ensemble fini. L’ensemble P(E) des parties de E est fini et : card P(E) = 2card E .

Démonstration

Posons n = card E et notons Pk (E) l’ensemble des parties de E de cardinal k pour k ∈ J0, nK ! n — nous venons de voir que Pk (E) est fini de cardinal . Evidemment, d’autre part, P(E) est la réunion k disjointe des ensembles Pk (E). Nous en déduisons aussitôt que P(E) est fini et que : card P(E) =

n X k=0

card Pk (E) =

n X k=0

n k

8

!

=

n X k=0

!

n k n−k 1 1 = (1 + 1)n = 2n = 2card E . k