M-CO-ENT-JMF

7/23/2019 M-CO-ENT-JMF

1/14

Cours de Mathematiques

Entiers naturels, denombrements

Sommaire


Sommaire

I Entiers naturels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

I.1 Lensemble N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

I.2 Raisonnement par recurrence . . . . . . . . . . . . . . . . . . . . . . . 2

I.3 Somme et produit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

I.4 Relation dordre et difference . . . . . . . . . . . . . . . . . . . . . . . 4

I.5 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

I.6 Pratique du raisonnement par recurrence . . . . . . . . . . . . . . . . 5

II Ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

II.1 Cardinal dun ensemble fini . . . . . . . . . . . . . . . . . . . . . . . . 7

II.2 Proprietes des cardinaux. . . . . . . . . . . . . . . . . . . . . . . . . . 9

III Denombrements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

III.1 Applications entre ensembles finis. . . . . . . . . . . . . . . . . . . . . 10

III.2 Arrangements et combinaisons . . . . . . . . . . . . . . . . . . . . . . 10

III.3 Binome de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

IV Ensembles denombrables . . . . . . . . . . . . . . . . . . . . . . . . . 13

Page 1 Jean-Michel Ferrard www.klubprepa.net cEduKlub S.A.

Tous droits de lauteur des uvres reserves. Sauf autorisation, la reproduction ainsi que toute utilisation des uvres autre que la consultationindividuelle et privee sont interdites.
http://www.klubprepa.net/


2/14



Partie I : Entiers naturels

I Entiers naturels

I.1 Lensemble NConformement au programme des classes preparatoires, lensemble IN est suppose connu, ainsique ses proprietes (operations + et , relation dordre).

Cependant, en voici une presentation minimale (ou presque) a partir de laquelle on pourraitretrouver toutes ses proprietes.

On admet lexistence dun ensemble IN, dont les elements sont appeles entiers naturels, tel que :

a. Successeur dun entier naturel

Il existe une application s: IN IN, appelee succession.

Limage par s dun entier naturel n est appelee le successeur de n.

b. Entier 0

Il existe un element de IN, note 0, qui na pas dantecedent par s.

On note 1 le successeur de 0, 2 celui de 1, 3 celui de 2, etc.

On note IN = IN {0}: cest lensemble des entiers naturels non nuls.

c. Predecesseur dun entier naturel non nul

Lapplication sest une bijection de IN sur IN {0}.

Tout nde IN est donc le successeur dun unique mde IN, appele le predecesseur de n.

d. Axiome de recurrenceSoit 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 elements,alors cette partie A est egale a IN tout entier.

Tout cela permet par exemple de definir une additionsur IN, de la maniere 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 definition precedente).

Pour tout nde IN

, on note n 1 le predecesseur de n. Ainsi m= n 1 n = m+ 1 . . .

Laxiome de recurrence secrit maintenant : Soit A une partie de IN, contenant 0.

On suppose que : n A, n+ 1 A. Alors A= IN.

I.2 Raisonnement par recurrence

SoitPun predicat, de referentiel IN.

Rappelons quon ecrit P(n) pour dire P(n) est vraie.




3/14




Recurrence 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 quune proprieteP(n) est vraie pour tous les entiers naturels :

On verifie que lentier 0 satisfait a la propriete : cest le pas initialde la recurrence.

On se donne ensuite un entier n, pour lequel on suppose que P(n) est vraie.

Cest lhypothese de recurrence.

On demontre alors que P(n+ 1) est vraie (cest le passage du rangn au rangn+ 1).

On exprime limplicationP(n) P(n+ 1) en disant que la proprieteP est hereditaire.

On conclut en annoncant que, par recurrence, la propriete est vraie pour tout entier n.

I.3 Somme et produit

Toutes les operations sur IN peuvent etre definies par recurrence (on la deja vu pour laddition).

Leurs proprietes peuvent etre etablies de la meme maniere.

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 element neutre : n IN, n+ 0 =n (cette propriete decoule de la definition).

Tout element de IN est regulier : (m,n,p) IN3, m+p = n+p m = n.

(m, n) IN2, m+n= 0 m = n = 0.

Multiplication

On definit un produitsur IN, en posant :

(m, n) IN2, m0 = 0, m(n+ 1) = mn+m

Une recurrence montre que mnest defini pour tout couple (m, n).

Toujours par recurrence, on peut alors verifier les proprietes suivantes :

La loi est distributivepar 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 element de IN est regulier : (m, n) IN2, p IN, mp= np m = n.

1 est element neutre : n IN, n1 =n.

Factorielle

On definit n! (factorielle n) par 0! = 1, et nIN, n! =n (n 1)!

Autrement dit : nIN, n! =n

k=1

k.




4/14




Exponentiation

On definit la notation mn : (m, n)IN2, m0 = 1, mn+1 =mn m.

On montre alors les proprietes suivantes par recurrence :

(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 dordre et difference

Definition

On pose : (m, n) IN2, m n p IN, m+p = n.

Les notations n m et m n sont bien sur equivalentes.

On note m < n pour ecrire : (m n) et (m=n).

Soit (m, n) dans IN2. On pose : [[m, n]] ={p IN, m p n}.

Proprietes

definit une relation dordre 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 possede un plus petit element.

Toute partie majoree non vide de IN possede un plus grand element.

La relation est compatibleavec les operations + et , ce qui signifie :

(m,n,p) IN : m n (m+p n+p) et (mp np)

Soustraction

Lexistence de la relation dordre et de laddition sur IN permettent de definir la differencep= n mde deux entiers naturels n et m.

Cette operation nest pas partout definie sur IN (lentier p nexiste que si m

n).

Soit (m, n) un couple dentiers naturels, tels que m n. Lentierp tel quem +p= n (uniquepar regularite) est appele differencede n et de m, et on note p= n m.

Cette notation generalise celle qui a ete utilisee au debut de ce chapitre pour definir lepredecesseur m= n 1 dun entier naturel non nul n.

Proprietes

On a (entre autres) les egalites suivantes, sous reserve que les differences existent dans IN :

(m,n,p) IN3, (m n) p= m (n+p). Cette quantite est notee m n p.

(m,n,p) IN3, (m n) +p= m (n p). Cette quantite est notee m n+p.

(m,n,p) IN3, (m+n) p= m+ (n p). Cette quantite est notee m+n p.




5/14




I.5 Division euclidienne

Definition

On dit que n divise m(ou que m est un multiplede n) si : q IN, m= nq.

On note alors n| m. On definit ainsi une relation dordre partiel sur IN.

Pour cette relation, 1 est le minimum de IN.

Definition

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) sappelle division euclidiennede mpar n.

Dans cette division, mest le dividende, nle diviseur, q le quotient, et r le reste.

Remarque

n| m (m= n = 0) ou (n= 0 et le reste dans la division de mpar nest nul).

I.6 Pratique du raisonnement par recurrence

Le raisonnement de recurrence admet plusieurs variantes, dont celle-ci, qui ne differe de loriginalque par le pas initial qui peut se situer en n0 (entier naturel) plutot quen 0 :

Soit n0 un entier naturel.

On supposeP(n0).On suppose egalement que : n n0,P(n) P(n+ 1).

Alors, n n0,P(n).

Une autre variante reside dans la maniere davancer dans la recurrence.

Il arrive en effet que lhypothese P(n) seule soit insuffisante pour demontrerP(n+ 1).

Le cas le plus frequent est celui de la recurrence double, ou le pas initial et lhypothese derecurrence portent sur deux entiers consecutifs.

Recurrence de pas double

Soit n0

un entier naturel.

On supposeP(n0) et P(n0+ 1).

On suppose egalement que : n n0, (P(n) etP(n+ 1)) P(n+ 2).

Alors, n n0,P(n).

Il reste a voir une derniere version du raisonnement par recurrence. Pour demontrer P(n+ 1),on peut en effet utiliser tout ou partie des hypotheses P(n0),P(n0+ 1), . . ., etP(n).

Recurrence forte

Soit n0 un entier naturel. On supposeP(n0).

On suppose aussi que : n n0, (P(n0), P(n0+ 1), . . . , P(n)) P(n+ 1).

Alors, n n0, P(n).




6/14




Voici enfin quelques conseils pour reussir un raisonnement par recurrence :

Ne pas oublier le pas initial (la propriete est souvent triviale, mais on doitla prouver).

Ne pas ecrire : Supposons que pour toutn, P(n). Montrons P(n+1) alors quil faut ecrire :Soit n un entier naturel ; on suppose P(n). Montrons P(n+ 1).

Bien articuler le pas initial et lhypothese de recurrence.

Si le pas initial est par exemple n0, et si on veut demontrer P(n) P(n+ 1), alors n doitetre superieur ou egal a n0. On peut tout a fait prouverP(n 1) P(n), mais dans ce casndoit etre strictement superieur a n0.

Bien separer le passage du rang n au rang n+ 1, ou lentier n est fixe, et la conclusionfinale (qui est obligatoire, et qui doit porter sur tous les entiers naturels n).




7/14



Partie II : Ensembles finis

II Ensembles finis

II.1 Cardinal dun ensemble finiPour tout entier naturel, on note En = {mIN, 1 m n}.

Dans les trois enonces 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.

PropositionIl existe une bijection de En sur Ep si et seulement si n= p.

Proposition

Soit nun entier naturel non nul, et fune application de En dans lui-meme.

Alors : f est bijective fest injective f est surjective.

On peut maintenant donner la definition dun ensemble fini.

Proposition

Un ensemble non vide Eest dit finisil existe une bijection de En sur E, avec n 1.Lentiern, sil existe, est unique et est appele 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) represente bien sur le nombre delements de E.

Dans la definition, on aurait pu aussi bien dire : sil existe une bijection de Esur En

Si m n, lintervalle [[m, n]] est fini de cardinal n m+ 1. En effet lapplication f definiepar f(k) =k m+ 1 est bijective de [[m, n]] sur Enm+1.

Sil existe une bijection f de Efini sur F, alors Fest fini et card (E) = card (F).

On peut caracteriser les parties finies de IN :

Proposition

Une partie A non vide de IN est finieelle est majoree. En particulier IN est infini.

On en deduit le resultat suivant :

Proposition

Soit Eun ensemble fini. Soit A une partie de E.

Alors A est un ensemble fini et card (A)card(E).

Plus precisement, on a card (A) = card (E) si et seulement si A= E.




8/14




Remarque

Si Eest infini, il peut exister des bijections de Esur une partie stricte de E.

Par exemple, lapplication n 2nest une bijection de IN sur lensemble des entiers pairs, etla succession nn+ 1 est une bijection de IN sur IN.

Les trois propositions suivantes peuvent permettre de montrer quun ensemble est fini.

Proposition

SoientE et F deux ensembles, E etant fini. Soit fune application de Evers 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 resultat precedent (on remplacef

(E

) parF

) :Proposition

Soit Eun ensemble fini. Soit Fun ensemble quelconque.

Soit fune application surjective de Esur F.

Alors F est fini, et card (F) card(E).

De plus on a card (F) = card (E) f est bijective.

Proposition

SoientE et F deux ensembles.

Soit fune application injective de E dans F.Si f(E) est fini, alors Eest fini et card (E) = card (f(E)).

Voici des resultats tres proches des precedents. Il sagit plutot ici de caracteriser lexistencedapplications injectives, surjectives ou bijectives entre deux ensembles dont lun est fini.

Proposition

SoientE et Fdeux ensembles non vides, lensemble F etant fini.

Il existe une injection de Edans F (Eest fini et card (E) card(F)).

PropositionSoientE et Fdeux ensembles non vides, lensemble E etant fini.

Il existe une surjection de Esur F (Fest fini et card (F) card(E)).

Il existe une bijection de Esur F (Fest fini et card (E) = card (F)).

Proposition

SoientE et F deux ensembles finis non vides de meme cardinal.

Soit fune application de Evers F.

f est bijective f est injective f est surjective.




9/14




II.2 Proprietes des cardinaux

On voit ici comment calculer le cardinal densembles construits a partir densembles finis.

Proposition (Reunion densembles finis disjoints)

Si E et Fsont finis disjoints, alors E Fest fini et card (E F) = card (E) + card (F).

Si E1, . . . , E n sont finis disjoints deux a deux,ni=1

Ei est fini et card (ni=1

Ei) =ni=1

card(Ei).

Proposition (Reunion de deux ensembles finis)

SiEetFsont finis, alors EFest fini et card (EF) = card (E)+card(F) card(EF).

En particulier : card (E F) card(E) + card (F), avec egalite E F =.

Proposition (Generalisation an ensembles finis)

Si E1, E2, . . . , E n sont finis, alorsni=1

Ei est fini et card (ni=1

Ei)ni=1

card(Ei).

On a legalite card (ni=1

Ei) =ni=1

card(Ei) les Ei sont disjoints deux a deux.

Le resultat precedent peut etre generalise (mais la demonstration est admise) :

Proposition (Formule du crible)

SoientE1, . . ., En des ensembles finis. Posons I={1, 2, . . . , n}.

On a card ( ni=1

Ei) =J I

(1)1+card(J) card(jJ

Ej)

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, Fdeux ensembles finis, et fune application de Evers F.Alors card (E) =

yF

card f-1

({y}).

Donc si tous les elements de F ont le meme nombre qdantecedents : card (E) =qcard (F).

Proposition (Produit cartesien densembles finis)

Si E et Fsont finis, alors E Fest fini et card (E F) = card (E)card(F).

Plus generalement, si E1, E2, . . ., En sont finis, alors card (ni=1

Ei) =ni=1

card(Ei).

En particulier, si Eest fini, alors pour tout n1 : card (En) = card (E)n.




10/14



Partie III : Denombrements

III Denombrements

III.1 Applications entre ensembles finisOn noteF(E, F) lensemble des applications dun ensemble Evers un ensemble F.

Proposition (Nombre dapplications entre deux ensembles finis)

Si E et Fsont finis non vides, F(E, F) est fini et card(F(E, F)) = card (F) card(E).

Ce resultat justifie que lon note souventFE lensembleF(E, F).

Proposition (Ensemble des parties dun ensemble fini)

Soit Eun ensemble fini, de cardinal n. AlorsP(E) est fini et card (P(E)) = 2n.

Proposition (Nombre dinjections ou de bijections entre deux ensembles finis)

SoientE et Fdeux ensembles finis non vides.

Notons card (E) =p, et card (F) =n, avec 1 p n.

Le nombre dinjections de Edans F est n!(np)!

En particulier, si card (E) = card (F) =n, le nombre de bijections de Edans F est n!

Cest le cas si E=F(les bijections de Esur Esont appelees permutations de E).

III.2 Arrangements et combinaisons

Definition

Soientp, n deux entiers tels que 0 p n.

On poseApn = n!

(np)! etCpn =

1p !A

pn =

n!p !(np)! C

pn est souvent note

n

p

.

On constate que, si 1 p n :

Apn =n(n 1) (n p+ 1)

Cpn = n(n1)(np+1)

p(p1)21

Par exemple : n IN, A 0n = 1, Ann =n!, C 0n =Cnn = 1.

n IN, A 1n =n, An1n =n!, C 1n =C

n1n =n.

On sait que si 1 p n,Apn represente le nombre dapplications injectives dun ensemble a pelements vers un ensemble a n elements.

Proposition (Arrangements)

Soit Fun ensemble fini de cardinal n 1. Soit p un entier verifiant 1 p n.

Un arrangement de p elements de F est un p-uplet (y1, y2, . . . , yp) forme de p elements deF, distincts deux a deux.

Le nombre darrangements de p elements de F estA pn (on parle souvent darrangements

de p elements parmi n).




11/14




Proposition (Combinaisons)

Soit Fun ensemble fini de cardinal n 1. Soit p un entier verifiant 0 p n.

Une combinaisonde p elements de Fest une partie de F, de cardinal p.Si p 1, elle peut donc secrire{y1, y2, . . . , yp}, ou y1, y2, . . ., yp sont distincts deux a deuxdans F(on parle souvent de combinaison sans repetitions).

Le nombre de combinaisons de p elements de Fest egal aCpn (on parle souvent de combi-naisons de p elements parmi n).

Proprietes fondamentales des coefficients CpnPour tous entiers n, p avec 0 p n :Cpn =C

npn .

Si 1 p n 1, alorsCpn =Cpn1 + C

p1n1.

Cette derniere formule, avecC 0n =Cnn = 1, permet de calculer lesC

pn de proche en proche.

On place souvent les Cpn dans un tableau triangulaire, dont les lignes et les colonnes sontnumerotees a partir de 0. Le coefficient Cpn vient alors se placer a lintersection de la lignedindice n et de la colonne dindice p.

Le tableau ci-dessous est connu sous le nom de triangle de Pascal :

p= 0 p= 1 p= 2 p= 3 p= 4 p= 5 p= 6 n= 0 1n= 1 1 1

n= 2 1 2 1n= 3 1 3 3 1n= 4 1 4 6 4 1n= 5 1 5 10 10 5 1n= 6 1 6 15 20 15 6 1

... ...

... ...

... ...

... . . . . . .

n C 0n C1n C

2n C

3n C

4n C

5n C

6n

. . ....

... ...

... ...

... ...

... . . .

Autres proprietes

Sous reserve que les coefficients ci-dessous soient definis, on a les egalites :

Cp+1n = npp+1C

pn, C

pn =

n

pCp1n1, C

pn =

n

npCpn1

III.3 Binome de Newton

Le resultat suivant est particulierement important.

Cest sans doute en utilisant la formule du binome quon a le plus de chances de rencontrer lescoefficientsCpn (qui pour cette raison sont appeles coefficients du binome).




12/14




Proposition (Formule du binome de Newton)

(x, y) lC2, n IN, (x+y)n =n

k=0

Ckn xk ynk.

En particulier : x lC, (1 +x)n =n

k=0Ckn x

k.




13/14



Partie IV : Ensembles denombrables

IV Ensembles denombrables

NB : la notion densemble denombrable est hors-programme des classes preparatoires.

Definition

Un ensemble Eest dit denombrablesil existe une bijection de IN sur E.

Un ensemble Eest dit au plus denombrablesil est fini ou denombrable.

Remarques

IN est evidemment lui-meme un ensemble denombrable.

IN est denombrable car la succession nn+ 1 est une bijection de IN sur IN.

De meme, lensemble des entiers pairs et celui des entiers impairs sont denombrables (considerer

les applicationsn2net n2n+ 1.) Tout ensemble denombrable est infini (car IN est lui-meme infini.)

Si Eest denombrable, et si on note n an une bijection de IN sur E, on peut donc ecrireE = {an, n IN}, les an etant distincts deux a deux. Le caractere denombrable de E estdonc une maniere de numeroter distinctement les differents elements de E.

Si E est denombrable (resp. au plus denombrable) et sil existe une bijection de E sur unensembleF, alors F est denombrable (resp. au plus denombrable).

Proposition (Parties dun ensemble denombrable)

Toute partie F dun ensemble denombrable Eest au plus denombrable.

Proposition (Produit cartesien densembles denombrables)

Lensemble IN IN est denombrable.

Si E1, . . . , E n sont denombrables, leur produit cartesienn

k=1

Ek est denombrable.

Proposition (Une caracterisation des ensembles au plus denombrables)

SoientEun ensemble denombrable. Un ensemble F non vide est au plus denombrable si etseulement sil existe une surjection de Esur F.

Remarques et consequences

La proposition precedente signifie quun ensemble non vide Eest au plus denombrable si etseulement sil peut secrire E={an, n IN}, (les an etant non necessairement distincts.)

Lensemble ZZ est denombrable car il est infini (il contient IN) et lapplication definie sur IN2

par f(m, n) =m n est une sujection de IN2 sur ZZ.

Lensemble lQ est denombrable car il est infini (il contient IN) et lapplication f definie surZZ IN par f(m, n) = m

nest une surjection de ZZ IN sur lQ.




14/14



Partie IV : Ensembles denombrables

Proposition (Reunions densembles au plus denombrables)

Soit (En)nINune suite densembles au plus denombrables.

Alors leur reunion F =nIN

En est un ensemble au plus denombrable.

Remarques

Si lun au moins des En est denombrable, alors F=nIN

En est denombrable.

Une unionfiniedensembles au plus denombrables est au plus denombrable : il suffit en effetde completer une famille finie E0, E1, . . . , E n par des Ek egaux par exemple a En.

Proposition

LensembleP(IN) est infini non denombrable.

Proposition

Lensemble IR est infini non denombrable.



Documents

M-CO-ENT-JMF