Cours de Mathématiques
Entiers naturels, dénombrements
Sommaire
Entiers naturels, dénombrements
Sommaire
I
II
Entiers naturels
I.1
I.2
I.3
I.4
I.5
I.6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
L’ensemble N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Raisonnement par récurrence . . . . . . . . . . . . . . . . . . . . . . .
Somme et produit
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Relation d’ordre et différence . . . . . . . . . . . . . . . . . . . . . . .
Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
Pratique du raisonnement par récurrence
Ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
Cardinal d’un ensemble fini
Propriétés des cardinaux . . . . . . . . . . . . . . . . . . . . . . . . . .
III Dénombrements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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ôme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
13
IV Ensembles dénombrables . . . . . . . . . . . . . . . . . . . . . . . . .
II.1
II.2
c(cid:13)EduKlub S.A.
Page 1
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie I : Entiers naturels
I Entiers naturels
I.1 L’ensemble N
Conformément au programme des classes préparatoires, l’ensemble IN est supposé connu, ainsi
que ses propriétés (opérations + et ×, relation d’ordre).
Cependant, en voici une présentation minimale (ou presque) à partir de laquelle on pourrait
retrouver toutes ses propriétés.
On admet l’existence d’un ensemble IN, dont les éléments sont appelés entiers naturels, tel que :
a. Successeur d’un entier naturel
Il existe une application s : IN → IN, appelée succession.
L’image par s d’un entier naturel n est appelée le successeur de n.
b. Entier 0
Il existe un élément de IN, noté 0, qui n’a pas d’antécédent 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édécesseur 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é le prédécesseur de n.
d. Axiome de récurrence
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 éléments,
alors cette partie A est égale à IN tout entier.
Tout cela permet par exemple de définir une addition sur IN, de la manière 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éfinition précédente).
Pour tout n de IN∗, on note n − 1 le prédécesseur de n. Ainsi m = n − 1 ⇔ n = m + 1 . . .
L’axiome de récurrence s’écrit 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écurrence
Soit P un prédicat, de référentiel IN.
Rappelons qu’on écrit P(n) pour dire “P(n) est vraie”.
c(cid:13)EduKlub S.A.
Page 2
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie I : Entiers naturels
Récurrence 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été P(n) est vraie pour tous les entiers naturels :
– On vérifie que l’entier 0 satisfait à la propriété : c’est le pas initial de la récurrence.
– On se donne ensuite un entier n, pour lequel on suppose que P(n) est vraie.
C’est l’hypothèse de récurrence.
– On démontre 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été P est héréditaire.
– On conclut en annonçant que, par récurrence, la propriété est vraie pour tout entier n.
I.3 Somme et produit
Toutes les opérations sur IN peuvent être définies par récurrence (on l’a déja vu pour l’addition).
Leurs propriétés peuvent être établies de la même manière.
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 élément neutre : ∀ n ∈ IN, n + 0 = n (cette propriété découle de la définition).
Tout élément de IN est régulier : ∀ (m, n, p) ∈ IN3, m + p = n + p ⇒ m = n.
∀ (m, n) ∈ IN2, m + n = 0 ⇔ m = n = 0.
Multiplication
On définit un produit sur IN, en posant :
∀ (m, n) ∈ IN2, m0 = 0, m(n + 1) = mn + m
Une récurrence montre que mn est défini pour tout couple (m, n).
Toujours par récurrence, on peut alors vérifier les propriétés suivantes :
La loi × est distributive par rapport à 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 élément de IN∗ est régulier : ∀ (m, n) ∈ IN2, ∀ p ∈ IN∗, mp = np ⇒ m = n.
1 est élément neutre : ∀ n ∈ IN, n1 = n.
Factorielle
On définit 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie I : Entiers naturels
Exponentiation
On définit la notation mn : ∀ (m, n) ∈ IN2, m0 = 1, mn+1 = mn m.
On montre alors les propriétés suivantes par récurrence :
∀ (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érence
Définition
On pose : ∀ (m, n) ∈ IN2, m ≤ n ⇔ ∃ p ∈ IN, m + p = n.
Les notations n ≥ m et m ≤ n sont bien sûr équivalentes.
On note m < n pour écrire : (m ≤ n) et (m 6= n).
Soit (m, n) dans IN2. On pose : [[m, n]] = {p ∈ IN, m ≤ p ≤ n}.
Propriétés
– ≤ définit 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ède un plus petit élément.
– Toute partie majorée non vide de IN possède un plus grand élément.
– La relation ≤ est compatible avec les opérations + 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éfinir la différence
p = n − m de deux entiers naturels n et m.
Cette “opération” n’est pas partout définie 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égularité) est appelé différence de n et de m, et on note p = n − m.
Publicité
Cette notation généralise celle qui a été utilisée au début de ce chapitre pour définir le
prédécesseur m = n − 1 d’un entier naturel non nul n.
Propriétés
On a (entre autres) les égalités suivantes, sous réserve que les différences existent dans IN :
∀ (m, n, p) ∈ IN3, (m − n) − p = m − (n + p). Cette quantité est notée m − n − p.
∀ (m, n, p) ∈ IN3, (m − n) + p = m − (n − p). Cette quantité est notée m − n + p.
∀ (m, n, p) ∈ IN3, (m + n) − p = m + (n − p). Cette quantité est notée m + n − p.
c(cid:13)EduKlub S.A.
Page 4
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie I : Entiers naturels
I.5 Division euclidienne
Définition
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éfinit ainsi une relation d’ordre partiel sur IN.
Pour cette relation, 1 est le minimum de IN.
Définition
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écurrence
Le raisonnement de récurrence admet plusieurs variantes, dont celle-ci, qui ne diffère de l’original
que par le “pas initial” qui peut se situer en n0 (entier naturel) plutôt qu’en 0 :
Soit n0 un entier naturel.
On suppose P(n0).
On suppose également que : ∀ n ≥ n0, P(n) ⇒ P(n + 1).
Alors, ∀ n ≥ n0, P(n).
Une autre variante réside dans la manière d’avancer dans la récurrence.
Il arrive en effet que l’hypothèse P(n) seule soit insuffisante pour démontrer P(n + 1).
Le cas le plus fréquent est celui de la récurrence double, ou le pas initial et l’hypothese de
récurrence portent sur deux entiers consécutifs.
Récurrence de pas double
Soit n0 un entier naturel.
On suppose P(n0) et P(n0 + 1).
On suppose également 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écurrence. Pour démontrer P(n + 1),
on peut en effet utiliser tout ou partie des hypothèses P(n0), P(n0 + 1), . . ., et P(n).
Récurrence 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie I : Entiers naturels
Voici enfin quelques conseils pour “réussir” un raisonnement par récurrence :
– Ne pas oublier le “pas initial” (la propriété est souvent triviale, mais on doit la prouver).
– Ne pas écrire : “Supposons que pour tout n, P(n). Montrons P(n+1)” alors qu’il faut écrire :
“Soit n un entier naturel ; on suppose P(n). Montrons P(n + 1)”.
– Bien articuler le pas initial et l’hypothèse de récurrence.
Si le pas initial est par exemple n0, et si on veut démontrer P(n) ⇒ P(n + 1), alors n doit
être supérieur ou égal a n0. On peut tout a fait prouver P(n − 1) ⇒ P(n), mais dans ce cas
n doit être strictement supérieur à n0.
– Bien séparer le “passage du rang n au rang n + 1”, où l’entier n est fixé, 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
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 énoncés 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ême.
Alors : f est bijective ⇔ f est injective ⇔ f est surjective.
On peut maintenant donner la définition 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é 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
– card (E) représente bien sûr le “nombre d’éléments” de E.
– Dans la définition, 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éfinie
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ériser les parties finies de IN :
Proposition
Une partie A non vide de IN est finie⇔elle est majorée. En particulier IN est infini.
On en déduit le résultat 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écisément, 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
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 étant 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ésultat précédent (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ésultats très proches des précédents. Il s’agit plutôt ici de caractériser 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 étant 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 étant 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ême 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie II : Ensembles finis
II.2 Propriétés des cardinaux
On voit ici comment calculer le cardinal d’ensembles construits à partir d’ensembles finis.
Proposition (Réunion 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 à deux,
Ei est fini et card (
Ei) =
card (Ei).
n
Publicité
S
i=1
n
S
i=1
n
P
i=1
Proposition (Réunion 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 égalité⇔ E ∩ F = ∅.
Proposition (Généralisation à n ensembles finis)
Si E1, E2, . . . , En sont finis, alors
On a l’égalité 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 à deux.
Le résultat précédent peut être généralisé (mais la démonstration 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 éléments de F ont le même nombre q d’antécédents : card (E) = q card (F ).
y∈F
Proposition (Produit cartésien d’ensembles finis)
Si E et F sont finis, alors E × F est fini et card (E × F ) = card (E) card (F ).
Plus généralement, 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie III : Dénombrements
III Dénombrements
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ésultat 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ées permutations de E).
III.2 Arrangements et combinaisons
Définition
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é (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
éléments vers un ensemble à n éléments.
n représente le nombre d’applications injectives d’un ensemble à p
Proposition (Arrangements)
Soit F un ensemble fini de cardinal n ≥ 1. Soit p un entier vérifiant 1 ≤ p ≤ n.
Un arrangement de p éléments de F est un p-uplet (y1, y2, . . . , yp) formé de p éléments de
F , distincts deux à deux.
Le nombre d’arrangements de p éléments de F est A p
de p éléments parmi n).
n (on parle souvent d’arrangements
c(cid:13)EduKlub S.A.
Page 10
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie III : Dénombrements
Proposition (Combinaisons)
Soit F un ensemble fini de cardinal n ≥ 1. Soit p un entier vérifiant 0 ≤ p ≤ n.
Une combinaison de p éléments de F est une partie de F , de cardinal p.
Si p ≥ 1, elle peut donc s’écrire {y1, y2, . . . , yp}, ou y1, y2, . . ., yp sont distincts deux a deux
dans F (on parle souvent de combinaison sans répétitions).
Le nombre de combinaisons de p éléments de F est égal à C p
naisons de p éléments parmi n).
n (on parle souvent de combi-
Propriétés 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ère formule, avec C 0
On place souvent les C p
numérotées à 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 à 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
Publicité
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
4
10
20
...
C 3
n
...
1
5
15
...
C 4
n
...
1
6
...
C 5
n
...
1
. . .
C 6
n
...
. . .
. . .
. . .
Autres propriétés
Sous réserve que les coefficients ci-dessous soient définis, on a les égalités :
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ôme de Newton
Le résultat suivant est particulièrement important.
C’est sans doute en utilisant la formule du binôme qu’on a le plus de chances de rencontrer les
coefficients C p
n (qui pour cette raison sont appelés coefficients du binôme).
c(cid:13)EduKlub S.A.
Page 11
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie III : Dénombrements
Proposition (Formule du binôme 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie IV : Ensembles dénombrables
IV Ensembles dénombrables
NB : la notion d’ensemble dénombrable est hors-programme des classes préparatoires.
Définition
Un ensemble E est dit dénombrable s’il existe une bijection de IN sur E.
Un ensemble E est dit au plus dénombrable s’il est fini ou dénombrable.
Remarques
– IN est évidemment lui-même un ensemble dénombrable.
IN∗ est dénombrable car la succession n 7→ n + 1 est une bijection de IN sur IN∗.
De même, l’ensemble des entiers pairs et celui des entiers impairs sont dénombrables (considérer
les applications n 7→ 2n et n 7→ 2n + 1.)
– Tout ensemble dénombrable est infini (car IN est lui-même infini.)
– Si E est dénombrable, et si on note n 7→ an une bijection de IN sur E, on peut donc écrire
E = {an, n ∈ IN}, les an étant distincts deux a deux. Le caractere dénombrable de E est
donc une manière de “numéroter” distinctement les différents éléments de E.
– Si E est dénombrable (resp. au plus dénombrable) et s’il existe une bijection de E sur un
ensemble F , alors F est dénombrable (resp. au plus dénombrable).
Proposition (Parties d’un ensemble dénombrable)
Toute partie F d’un ensemble dénombrable E est au plus dénombrable.
Proposition (Produit cartésien d’ensembles dénombrables)
L’ensemble IN × IN est dénombrable.
Si E1, . . . , En sont dénombrables, leur produit cartésien
n
Q
k=1
Ek est dénombrable.
Proposition (Une caractérisation des ensembles au plus dénombrables)
Soient E un ensemble dénombrable. Un ensemble F non vide est au plus dénombrable si et
seulement s’il existe une surjection de E sur F .
Remarques et conséquences
– La proposition précédente signifie qu’un ensemble non vide E est au plus dénombrable si et
seulement s’il peut s’écrire E = {an, n ∈ IN}, (les an étant non nécessairement distincts.)
– L’ensemble ZZ est dénombrable car il est infini (il contient IN) et l’application définie sur IN2
par f (m, n) = m − n est une sujection de IN2 sur ZZ.
– L’ensemble lQ est dénombrable car il est infini (il contient IN) et l’application f définie 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éservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Cours de Mathématiques
Entiers naturels, dénombrements
Partie IV : Ensembles dénombrables
Proposition (Réunions d’ensembles au plus dénombrables)
Soit (En)n∈IN une suite d’ensembles au plus dénombrables.
Alors leur réunion F = S
n∈IN
En est un ensemble au plus dénombrable.
Remarques
– Si l’un au moins des En est dénombrable, alors F = S
n∈IN
En est dénombrable.
– Une union finie d’ensembles au plus dénombrables est au plus dénombrable : il suffit en effet
de compléter une famille finie E0, E1, . . . , En par des Ek égaux par exemple à En.
Proposition
L’ensemble P(IN) est infini non dénombrable.
Proposition
L’ensemble IR est infini non dénombrable.
c(cid:13)EduKlub S.A.
Page 14
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard