Cours de Math´ematiques
Entiers naturels, d´enombrements
Sommaire
Entiers naturels, d´enombrements
Sommaire
I
II
Entiers naturels
I.1
I.2
I.3
I.4
I.5
I.6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
L’ensemble N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Raisonnement par r´ecurrence . . . . . . . . . . . . . . . . . . . . . . .
Somme et produit
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Relation d’ordre et diff´erence . . . . . . . . . . . . . . . . . . . . . . .
Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
Pratique du raisonnement par r´ecurrence
Ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
Cardinal d’un ensemble fini
Propri´et´es des cardinaux . . . . . . . . . . . . . . . . . . . . . . . . . .
III D´enombrements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
2
3
4
5
5
7
7
9
10
III.1 Applications entre ensembles finis . . . . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . . . . 10
III.2 Arrangements et combinaisons
III.3 Binˆome de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
13
IV Ensembles d´enombrables . . . . . . . . . . . . . . . . . . . . . . . . .
II.1
II.2
c(cid:13)EduKlub S.A.
Page 1
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie I : Entiers naturels
I Entiers naturels
I.1 L’ensemble N
Conform´ement au programme des classes pr´eparatoires, l’ensemble IN est suppos´e connu, ainsi
que ses propri´et´es (op´erations + et ×, relation d’ordre).
Cependant, en voici une pr´esentation minimale (ou presque) `a partir de laquelle on pourrait
retrouver toutes ses propri´et´es.
On admet l’existence d’un ensemble IN, dont les ´el´ements sont appel´es entiers naturels, tel que :
a. Successeur d’un entier naturel
Il existe une application s : IN → IN, appel´ee succession.
L’image par s d’un entier naturel n est appel´ee le successeur de n.
b. Entier 0
Il existe un ´el´ement de IN, not´e 0, qui n’a pas d’ant´ec´edent par s.
On note 1 le successeur de 0, 2 celui de 1, 3 celui de 2, etc.
On note IN∗ = IN − {0} : c’est l’ensemble des entiers naturels non nuls.
c. Pr´ed´ecesseur d’un entier naturel non nul
L’application s est une bijection de IN sur IN − {0}.
Tout n de IN∗ est donc le successeur d’un unique m de IN, appel´e le pr´ed´ecesseur de n.
d. Axiome de r´ecurrence
Soit A une partie de IN telle que : 0 ∈ A et ∀ n ∈ IN, n ∈ A ⇒ s(n) ∈ A. Alors A = IN.
Autrement dit, si une partie A de IN contient 0 et le successeur de chacun de ses ´el´ements,
alors cette partie A est ´egale `a IN tout entier.
Tout cela permet par exemple de d´efinir une addition sur IN, de la mani`ere suivante :
∀ (m, n) ∈ IN2, m + 0 = m, m + s(n) = s(m + n)
On constate que : ∀ m ∈ IN, s(m) = m + 1 (poser n = 0 dans la d´efinition pr´ec´edente).
Pour tout n de IN∗, on note n − 1 le pr´ed´ecesseur de n. Ainsi m = n − 1 ⇔ n = m + 1 . . .
L’axiome de r´ecurrence s’´ecrit maintenant :
( Soit A une partie de IN, contenant 0.
On suppose que : ∀ n ∈ A, n + 1 ∈ A. Alors A = IN.
I.2 Raisonnement par r´ecurrence
Soit P un pr´edicat, de r´ef´erentiel IN.
Rappelons qu’on ´ecrit P(n) pour dire “P(n) est vraie”.
c(cid:13)EduKlub S.A.
Page 2
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie I : Entiers naturels
R´ecurrence simple (ou faible)
(
On suppose P(0) et, pour tout entier n, P(n) ⇒ P(n + 1).
Alors, pour tout entier n, P(n).
Voici donc comment montrer qu’une propri´et´e P(n) est vraie pour tous les entiers naturels :
– On v´erifie que l’entier 0 satisfait `a la propri´et´e : c’est le pas initial de la r´ecurrence.
– On se donne ensuite un entier n, pour lequel on suppose que P(n) est vraie.
C’est l’hypoth`ese de r´ecurrence.
– On d´emontre alors que P(n + 1) est vraie (c’est le “passage du rang n au rang n + 1”).
On exprime l’implication P(n) ⇒ P(n + 1) en disant que la propri´et´e P est h´er´editaire.
– On conclut en annon¸cant que, par r´ecurrence, la propri´et´e est vraie pour tout entier n.
I.3 Somme et produit
Toutes les op´erations sur IN peuvent ˆetre d´efinies par r´ecurrence (on l’a d´eja vu pour l’addition).
Leurs propri´et´es peuvent ˆetre ´etablies de la mˆeme mani`ere.
Addition
La loi + est associative : ∀ (m, n, p) ∈ IN3, m + (n + p) = (m + n) + p.
La loi + est commutative : ∀ (m, n) ∈ IN2, m + n = n + m.
0 est ´el´ement neutre : ∀ n ∈ IN, n + 0 = n (cette propri´et´e d´ecoule de la d´efinition).
Tout ´el´ement de IN est r´egulier : ∀ (m, n, p) ∈ IN3, m + p = n + p ⇒ m = n.
∀ (m, n) ∈ IN2, m + n = 0 ⇔ m = n = 0.
Multiplication
On d´efinit un produit sur IN, en posant :
∀ (m, n) ∈ IN2, m0 = 0, m(n + 1) = mn + m
Une r´ecurrence montre que mn est d´efini pour tout couple (m, n).
Toujours par r´ecurrence, on peut alors v´erifier les propri´et´es suivantes :
La loi × est distributive par rapport `a la loi + :
∀ (m, n, p) ∈ IN3, m(n + p) = mp + mp.
La loi × est associative : ∀ (m, n, p) ∈ IN3, m(np) = (mn)p.
La loi × est commutative : ∀ (m, n) ∈ IN2, mn = nm.
Tout ´el´ement de IN∗ est r´egulier : ∀ (m, n) ∈ IN2, ∀ p ∈ IN∗, mp = np ⇒ m = n.
1 est ´el´ement neutre : ∀ n ∈ IN, n1 = n.
Factorielle
On d´efinit n! (factorielle n) par 0! = 1, et ∀ n ∈ IN∗, n! = n (n − 1)!
n
Y
Autrement dit : ∀ n ∈ IN∗, n! =
k.
k=1
c(cid:13)EduKlub S.A.
Page 3
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Publicité
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie I : Entiers naturels
Exponentiation
On d´efinit la notation mn : ∀ (m, n) ∈ IN2, m0 = 1, mn+1 = mn m.
On montre alors les propri´et´es suivantes par r´ecurrence :
∀ (m, n, p) ∈ IN3 : mn mp = mn+p, (mn)p = mnp, (mn)p = mp np.
∀ n ∈ IN, n1 = n, 1n = 1.
∀ n ∈ IN∗, 0n = 0 (mais par convention 00 = 1).
Remarques
mn = 1 ⇔ m = n = 1.
mn = 0 ⇔ (m = 0) ou (n = 0).
I.4 Relation d’ordre et diff´erence
D´efinition
On pose : ∀ (m, n) ∈ IN2, m ≤ n ⇔ ∃ p ∈ IN, m + p = n.
Les notations n ≥ m et m ≤ n sont bien sˆur ´equivalentes.
On note m < n pour ´ecrire : (m ≤ n) et (m 6= n).
Soit (m, n) dans IN2. On pose : [[m, n]] = {p ∈ IN, m ≤ p ≤ n}.
Propri´et´es
– ≤ d´efinit une relation d’ordre total sur IN.
– ∀ (m, n) ∈ IN2 : m < n ⇔ m + 1 ≤ n ⇔ m ≤ n − 1.
– 0 est le minimum de IN.
– Toute partie non vide de IN poss`ede un plus petit ´el´ement.
– Toute partie major´ee non vide de IN poss`ede un plus grand ´el´ement.
– La relation ≤ est compatible avec les op´erations + et ×, ce qui signifie :
∀ (m, n, p) ∈ IN : m ≤ n ⇒ (m + p ≤ n + p) et (mp ≤ np)
Soustraction
L’existence de la relation d’ordre et de l’addition sur IN permettent de d´efinir la diff´erence
p = n − m de deux entiers naturels n et m.
Cette “op´eration” n’est pas partout d´efinie sur IN (l’entier p n’existe que si m ≤ n).
Soit (m, n) un couple d’entiers naturels, tels que m ≤ n. L’entier p tel que m + p = n (unique
par r´egularit´e) est appel´e diff´erence de n et de m, et on note p = n − m.
Cette notation g´en´eralise celle qui a ´et´e utilis´ee au d´ebut de ce chapitre pour d´efinir le
pr´ed´ecesseur m = n − 1 d’un entier naturel non nul n.
Propri´et´es
On a (entre autres) les ´egalit´es suivantes, sous r´eserve que les diff´erences existent dans IN :
∀ (m, n, p) ∈ IN3, (m − n) − p = m − (n + p). Cette quantit´e est not´ee m − n − p.
∀ (m, n, p) ∈ IN3, (m − n) + p = m − (n − p). Cette quantit´e est not´ee m − n + p.
∀ (m, n, p) ∈ IN3, (m + n) − p = m + (n − p). Cette quantit´e est not´ee m + n − p.
c(cid:13)EduKlub S.A.
Page 4
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie I : Entiers naturels
I.5 Division euclidienne
D´efinition
On dit que n divise m (ou que m est un multiple de n) si : ∃ q ∈ IN, m = nq.
On note alors n | m. On d´efinit ainsi une relation d’ordre partiel sur IN.
Pour cette relation, 1 est le minimum de IN.
D´efinition
Soit (m, n) dans IN × IN∗.
Il existe un unique couple (q, r) de IN2 tel que : (m = nq + r) et (r ≤ n − 1)
Le passage du couple (m, n) au couple (q, r) s’appelle division euclidienne de m par n.
Dans cette division, m est le dividende, n le diviseur, q le quotient, et r le reste.
Remarque
n | m ⇔ (m = n = 0) ou (n 6= 0 et le reste dans la division de m par n est nul).
I.6 Pratique du raisonnement par r´ecurrence
Le raisonnement de r´ecurrence admet plusieurs variantes, dont celle-ci, qui ne diff`ere de l’original
que par le “pas initial” qui peut se situer en n0 (entier naturel) plutˆot qu’en 0 :
Soit n0 un entier naturel.
On suppose P(n0).
On suppose ´egalement que : ∀ n ≥ n0, P(n) ⇒ P(n + 1).
Alors, ∀ n ≥ n0, P(n).
Une autre variante r´eside dans la mani`ere d’avancer dans la r´ecurrence.
Il arrive en effet que l’hypoth`ese P(n) seule soit insuffisante pour d´emontrer P(n + 1).
Le cas le plus fr´equent est celui de la r´ecurrence double, ou le pas initial et l’hypothese de
r´ecurrence portent sur deux entiers cons´ecutifs.
R´ecurrence de pas double
Soit n0 un entier naturel.
On suppose P(n0) et P(n0 + 1).
On suppose ´egalement que : ∀ n ≥ n0, (P(n) et P(n + 1)) ⇒ P(n + 2).
Alors, ∀ n ≥ n0, P(n).
Il reste a voir une derniere version du raisonnement par r´ecurrence. Pour d´emontrer P(n + 1),
on peut en effet utiliser tout ou partie des hypoth`eses P(n0), P(n0 + 1), . . ., et P(n).
R´ecurrence forte
Soit n0 un entier naturel. On suppose P(n0).
On suppose aussi que : ∀ n ≥ n0, (P(n0), P(n0 + 1), . . . , P(n)) ⇒ P(n + 1).
Alors, ∀ n ≥ n0, P(n).
c(cid:13)EduKlub S.A.
Page 5
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie I : Entiers naturels
Voici enfin quelques conseils pour “r´eussir” un raisonnement par r´ecurrence :
– Ne pas oublier le “pas initial” (la propri´et´e est souvent triviale, mais on doit la prouver).
– Ne pas ´ecrire : “Supposons que pour tout n, P(n). Montrons P(n+1)” alors qu’il faut ´ecrire :
“Soit n un entier naturel ; on suppose P(n). Montrons P(n + 1)”.
– Bien articuler le pas initial et l’hypoth`ese de r´ecurrence.
Si le pas initial est par exemple n0, et si on veut d´emontrer P(n) ⇒ P(n + 1), alors n doit
ˆetre sup´erieur ou ´egal a n0. On peut tout a fait prouver P(n − 1) ⇒ P(n), mais dans ce cas
n doit ˆetre strictement sup´erieur `a n0.
– Bien s´eparer le “passage du rang n au rang n + 1”, o`u l’entier n est fix´e, et la conclusion
finale (qui est obligatoire, et qui doit porter sur tous les entiers naturels n).
c(cid:13)EduKlub S.A.
Page 6
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie II : Ensembles finis
II Ensembles finis
II.1 Cardinal d’un ensemble fini
Pour tout entier naturel, on note En = {m ∈ IN, 1 ≤ m ≤ n}.
Dans les trois ´enonc´es suivants, n et p sont des entiers naturels non nuls.
Proposition
Il existe une injection de En dans Ep si et seulement si n ≤ p.
Proposition
Il existe une surjection de En sur Ep si et seulement si n ≥ p.
Proposition
Il existe une bijection de En sur Ep si et seulement si n = p.
Proposition
Soit n un entier naturel non nul, et f une application de En dans lui-mˆeme.
Alors : f est bijective ⇔ f est injective ⇔ f est surjective.
On peut maintenant donner la d´efinition d’un ensemble fini.
Proposition
Un ensemble non vide E est dit fini s’il existe une bijection de En sur E, avec n ≥ 1.
L’entier n, s’il existe, est unique et est appel´e le cardinal de E. On note n = card (E).
Par convention, on dit que ∅ est fini de cardinal nul. Un ensemble non fini est dit infini.
Remarques
Publicité
– card (E) repr´esente bien sˆur le “nombre d’´el´ements” de E.
– Dans la d´efinition, on aurait pu aussi bien dire : “ s’il existe une bijection de E sur En”
– Si m ≤ n, l’intervalle [[m, n]] est fini de cardinal n − m + 1. En effet l’application f d´efinie
par f (k) = k − m + 1 est bijective de [[m, n]] sur En−m+1.
– S’il existe une bijection f de E fini sur F , alors F est fini et card (E) = card (F ).
On peut caract´eriser les parties finies de IN :
Proposition
Une partie A non vide de IN est finie⇔elle est major´ee. En particulier IN est infini.
On en d´eduit le r´esultat suivant :
Proposition
Soit E un ensemble fini. Soit A une partie de E.
Alors A est un ensemble fini et card (A) ≤ card (E).
Plus pr´ecis´ement, on a card (A) = card (E) si et seulement si A = E.
c(cid:13)EduKlub S.A.
Page 7
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie II : Ensembles finis
Remarque
Si E est infini, il peut exister des bijections de E sur une partie stricte de E.
Par exemple, l’application n 7→ 2n est une bijection de IN sur l’ensemble des entiers pairs, et
la succession n 7→ n + 1 est une bijection de IN sur IN∗.
Les trois propositions suivantes peuvent permettre de montrer qu’un ensemble est fini.
Proposition
Soient E et F deux ensembles, E ´etant fini. Soit f une application de E vers F .
Alors f (E) est fini, et card (f (E)) ≤ card (E).
De plus on a card (f (E)) = card (E) si et seulement si f est injective.
Voici un cas particulier du r´esultat pr´ec´edent (on remplace f (E) par F ) :
Proposition
Soit E un ensemble fini. Soit F un ensemble quelconque.
Soit f une application surjective de E sur F .
Alors F est fini, et card (F ) ≤ card (E).
De plus on a card (F ) = card (E) ⇔ f est bijective.
Proposition
Soient E et F deux ensembles.
Soit f une application injective de E dans F .
Si f (E) est fini, alors E est fini et card (E) = card (f (E)).
Voici des r´esultats tr`es proches des pr´ec´edents. Il s’agit plutˆot ici de caract´eriser l’existence
d’applications injectives, surjectives ou bijectives entre deux ensembles dont l’un est fini.
Proposition
Soient E et F deux ensembles non vides, l’ensemble F ´etant fini.
Il existe une injection de E dans F ⇔ (E est fini et card (E) ≤ card (F )).
Proposition
Soient E et F deux ensembles non vides, l’ensemble E ´etant fini.
Il existe une surjection de E sur F ⇔ (F est fini et card (F ) ≤ card (E)).
Il existe une bijection de E sur F ⇔ (F est fini et card (E) = card (F )).
Proposition
Soient E et F deux ensembles finis non vides de mˆeme cardinal.
Soit f une application de E vers F .
f est bijective ⇔ f est injective ⇔ f est surjective.
c(cid:13)EduKlub S.A.
Page 8
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie II : Ensembles finis
II.2 Propri´et´es des cardinaux
On voit ici comment calculer le cardinal d’ensembles construits `a partir d’ensembles finis.
Proposition (R´eunion d’ensembles finis disjoints)
Si E et F sont finis disjoints, alors E ∪ F est fini et card (E ∪ F ) = card (E) + card (F ).
Si E1, . . . , En sont finis disjoints deux `a deux,
Ei est fini et card (
Ei) =
card (Ei).
n
S
i=1
n
S
i=1
n
P
i=1
Proposition (R´eunion de deux ensembles finis)
Si E et F sont finis, alors E ∪F est fini et card (E ∪F ) = card (E)+card (F )−card (E ∩F ).
En particulier : card (E ∪ F ) ≤ card (E) + card (F ), avec ´egalit´e⇔ E ∩ F = ∅.
Proposition (G´en´eralisation `a n ensembles finis)
Si E1, E2, . . . , En sont finis, alors
On a l’´egalit´e card (
n
S
i=1
Ei) =
n
P
i=1
n
S
i=1
Ei est fini et card (
n
S
i=1
Ei) ≤
n
P
i=1
card (Ei).
card (Ei) ⇔ les Ei sont disjoints deux `a deux.
Le r´esultat pr´ec´edent peut ˆetre g´en´eralis´e (mais la d´emonstration est admise) :
Proposition (Formule du crible)
Soient E1, . . ., En des ensembles finis. Posons I = {1, 2, . . . , n}.
On a card (
n
S
i=1
Ei) = P
(−1)1+card (J) card ( T
Ej)
J ⊂ I
j∈J
Par exemple, si E, F , G sont trois ensembles finis :
card (E ∪ F ∪ G) = card (E) + card (F ) + card (G)
− card (E ∩ F ) − card (E ∩ G) − card (F ∩ G)
+ card (E ∩ F ∩ G).
Proposition (Principe des bergers)
Soit E, F deux ensembles finis, et f une application de E vers F .
Alors card (E) = P
-1
card f
({y}).
Donc si tous les ´el´ements de F ont le mˆeme nombre q d’ant´ec´edents : card (E) = q card (F ).
y∈F
Proposition (Produit cart´esien d’ensembles finis)
Si E et F sont finis, alors E × F est fini et card (E × F ) = card (E) card (F ).
Plus g´en´eralement, si E1, E2, . . ., En sont finis, alors card (
n
Q
i=1
Ei) =
n
Q
i=1
card (Ei).
En particulier, si E est fini, alors pour tout n ≥ 1 : card (En) = card (E)n.
c(cid:13)EduKlub S.A.
Page 9
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
Publicité
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie III : D´enombrements
III D´enombrements
III.1 Applications entre ensembles finis
On note F(E, F ) l’ensemble des applications d’un ensemble E vers un ensemble F .
Proposition (Nombre d’applications entre deux ensembles finis)
Si E et F sont finis non vides, F(E, F ) est fini et card (F(E, F )) = card (F ) card (E).
Ce r´esultat justifie que l’on note souvent F E l’ensemble F(E, F ).
Proposition (Ensemble des parties d’un ensemble fini)
Soit E un ensemble fini, de cardinal n. Alors P(E) est fini et card (P(E)) = 2n.
Proposition (Nombre d’injections ou de bijections entre deux ensembles finis)
Soient E et F deux ensembles finis non vides.
Notons card (E) = p, et card (F ) = n, avec 1 ≤ p ≤ n.
Le nombre d’injections de E dans F est
n!
(n−p)!·
En particulier, si card (E) = card (F ) = n, le nombre de bijections de E dans F est n!
C’est le cas si E = F (les bijections de E sur E sont appel´ees permutations de E).
III.2 Arrangements et combinaisons
D´efinition
Soient p, n deux entiers tels que 0 ≤ p ≤ n.
(n−p)! et C p
On pose A p
n = n!
n = 1
p !A p
On constate que, si 1 ≤ p ≤ n :
(
Par exemple :
∀ n ∈ IN, A 0
∀ n ∈ IN∗, A 1
(cid:1).
n est souvent not´e (cid:0)n
p
n!
n =
p !(n−p)!· C p
n = n(n − 1) · · · (n − p + 1)
n(n−1)···(n−p+1)
p(p−1)···2·1
( A p
C p
n =
n = n!, C 0
n = 1, A n
n = n!, C 1
n = n, A n−1
n = C n
n = 1.
n = C n−1
n = n.
On sait que si 1 ≤ p ≤ n, A p
´el´ements vers un ensemble `a n ´el´ements.
n repr´esente le nombre d’applications injectives d’un ensemble `a p
Proposition (Arrangements)
Soit F un ensemble fini de cardinal n ≥ 1. Soit p un entier v´erifiant 1 ≤ p ≤ n.
Un arrangement de p ´el´ements de F est un p-uplet (y1, y2, . . . , yp) form´e de p ´el´ements de
F , distincts deux `a deux.
Le nombre d’arrangements de p ´el´ements de F est A p
de p ´el´ements parmi n).
n (on parle souvent d’arrangements
c(cid:13)EduKlub S.A.
Page 10
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie III : D´enombrements
Proposition (Combinaisons)
Soit F un ensemble fini de cardinal n ≥ 1. Soit p un entier v´erifiant 0 ≤ p ≤ n.
Une combinaison de p ´el´ements de F est une partie de F , de cardinal p.
Si p ≥ 1, elle peut donc s’´ecrire {y1, y2, . . . , yp}, ou y1, y2, . . ., yp sont distincts deux a deux
dans F (on parle souvent de combinaison sans r´ep´etitions).
Le nombre de combinaisons de p ´el´ements de F est ´egal `a C p
naisons de p ´el´ements parmi n).
n (on parle souvent de combi-
Propri´et´es fondamentales des coefficients C p
n
( Pour tous entiers n, p avec 0 ≤ p ≤ n : C p
Si 1 ≤ p ≤ n − 1, alors C p
n = C p
n = C n−p
n−1 + C p−1
n−1 .
n
.
n = C n
Cette derni`ere formule, avec C 0
On place souvent les C p
num´erot´ees `a partir de 0. Le coefficient C p
d’indice n et de la colonne d’indice p.
Le tableau ci-dessous est connu sous le nom de “triangle de Pascal” :
n de proche en proche.
n dans un tableau triangulaire, dont les lignes et les colonnes sont
n vient alors se placer `a l’intersection de la ligne
n = 1, permet de calculer les C p
p = 0 p = 1 p = 2 p = 3 p = 4 p = 5 p = 6
· · ·
n = 0
n = 1
n = 2
n = 3
n = 4
n = 5
n = 6
...
n
...
1
1
1
1
1
1
1
...
C 0
n
...
1
2
3
4
5
6
...
C 1
n
...
1
3
6
10
15
...
C 2
n
...
1
Publicité
4
10
20
...
C 3
n
...
1
5
15
...
C 4
n
...
1
6
...
C 5
n
...
1
. . .
C 6
n
...
. . .
. . .
. . .
Autres propri´et´es
Sous r´eserve que les coefficients ci-dessous soient d´efinis, on a les ´egalit´es :
C p+1
n = n−p
p+1 C p
n , C p
n = n
p C p−1
n−1 , C p
n = n
n−p C p
n−1
III.3 Binˆome de Newton
Le r´esultat suivant est particuli`erement important.
C’est sans doute en utilisant la formule du binˆome qu’on a le plus de chances de rencontrer les
coefficients C p
n (qui pour cette raison sont appel´es coefficients du binˆome).
c(cid:13)EduKlub S.A.
Page 11
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie III : D´enombrements
Proposition (Formule du binˆome de Newton)
∀ (x, y) ∈ lC2, ∀ n ∈ IN, (x + y)n =
En particulier : ∀ x ∈ lC, (1 + x)n =
n
P
k=0
C k
n
P
k=0
n xk yn−k.
C k
n xk.
c(cid:13)EduKlub S.A.
Page 12
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie IV : Ensembles d´enombrables
IV Ensembles d´enombrables
NB : la notion d’ensemble d´enombrable est hors-programme des classes pr´eparatoires.
D´efinition
Un ensemble E est dit d´enombrable s’il existe une bijection de IN sur E.
Un ensemble E est dit au plus d´enombrable s’il est fini ou d´enombrable.
Remarques
– IN est ´evidemment lui-mˆeme un ensemble d´enombrable.
IN∗ est d´enombrable car la succession n 7→ n + 1 est une bijection de IN sur IN∗.
De mˆeme, l’ensemble des entiers pairs et celui des entiers impairs sont d´enombrables (consid´erer
les applications n 7→ 2n et n 7→ 2n + 1.)
– Tout ensemble d´enombrable est infini (car IN est lui-mˆeme infini.)
– Si E est d´enombrable, et si on note n 7→ an une bijection de IN sur E, on peut donc ´ecrire
E = {an, n ∈ IN}, les an ´etant distincts deux a deux. Le caractere d´enombrable de E est
donc une mani`ere de “num´eroter” distinctement les diff´erents ´el´ements de E.
– Si E est d´enombrable (resp. au plus d´enombrable) et s’il existe une bijection de E sur un
ensemble F , alors F est d´enombrable (resp. au plus d´enombrable).
Proposition (Parties d’un ensemble d´enombrable)
Toute partie F d’un ensemble d´enombrable E est au plus d´enombrable.
Proposition (Produit cart´esien d’ensembles d´enombrables)
L’ensemble IN × IN est d´enombrable.
Si E1, . . . , En sont d´enombrables, leur produit cart´esien
n
Q
k=1
Ek est d´enombrable.
Proposition (Une caract´erisation des ensembles au plus d´enombrables)
Soient E un ensemble d´enombrable. Un ensemble F non vide est au plus d´enombrable si et
seulement s’il existe une surjection de E sur F .
Remarques et cons´equences
– La proposition pr´ec´edente signifie qu’un ensemble non vide E est au plus d´enombrable si et
seulement s’il peut s’´ecrire E = {an, n ∈ IN}, (les an ´etant non n´ecessairement distincts.)
– L’ensemble ZZ est d´enombrable car il est infini (il contient IN) et l’application d´efinie sur IN2
par f (m, n) = m − n est une sujection de IN2 sur ZZ.
– L’ensemble lQ est d´enombrable car il est infini (il contient IN) et l’application f d´efinie sur
n est une surjection de ZZ × IN∗ sur lQ.
ZZ × IN∗ par f (m, n) = m
c(cid:13)EduKlub S.A.
Page 13
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Math´ematiques
Entiers naturels, d´enombrements
Partie IV : Ensembles d´enombrables
Proposition (R´eunions d’ensembles au plus d´enombrables)
Soit (En)n∈IN une suite d’ensembles au plus d´enombrables.
Alors leur r´eunion F = S
n∈IN
En est un ensemble au plus d´enombrable.
Remarques
– Si l’un au moins des En est d´enombrable, alors F = S
n∈IN
En est d´enombrable.
– Une union finie d’ensembles au plus d´enombrables est au plus d´enombrable : il suffit en effet
de compl´eter une famille finie E0, E1, . . . , En par des Ek ´egaux par exemple `a En.
Proposition
L’ensemble P(IN) est infini non d´enombrable.
Proposition
L’ensemble IR est infini non d´enombrable.
c(cid:13)EduKlub S.A.
Page 14
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard