[PDF] Dénombrement La formule sur le nombre

View - Download Dénombrement

Previous PDF

Next PDF

Chapitre 1

Dénombrement

Objectifs du chapitre

1. A tra versl"axiomatisation de Peano de N, rappeller les principes de récurrence forte et faible. 2. Définir la notion de cardinal et les opérations sur les cardinaux. F ormuledu crible. 3.

Notion de dénombrabilité.

4. Arrangements, permutations et combinaisons. F ormuledu binôme de Ne wton.

1.1 Entiers naturels et raisonnement par récurrence

On admet l"existence d"un ensembleNappeléensemble des entiers naturels, non vide, totalement ordonné et vérifiant

lesaxiomes de Peano1: 1. T outepartie non vide de Na un plus petit élément. 2. T outepartie non vide de Nmajorée admet un plus grand élément. 3. L "ensembleNn"admet pas de plus grand élément. Proposition 1.1.1.De manière immédiate on déduit les propriétés suivantes : 1. L "ensembleNadmet un plus petit élément noté 0. 2.

L "ensembleNnf0gadmet un plus petit élément noté 1, etc... On peut ainsi nommer les entiers successifs.

3.

P ourtout n 2N, la partiefp2N;p>nga un plus petit élément appelésuccesseurde n et noté n+1.

!On a ainsi l"amorce de l"addition deN. 4.

P ourtout n 2N, la partiefp2N;p L"existence d"un minimum induit le principe de récurrence.

Théorème 1.1.2(Récurrence faible).Soit P(n)une proposition dépendant d"un entier naturel n.

S"il existe un entier n

0tel que

la pr opositionP (n0)est vraie, pour tout entier n n0, la proposition "P(n))P(n+1)" est vraie alors, pour tout entier nn0, la proposition P(n)est vraie.

Démonstration.On considère l"ensemble

fn2Njnn0etP(n)fauxg:

On souhaite montrer que cet ensemble est vide. Supposons qu"il soit non vide. Il admet donc un plus petit élément noté

n

1=n0+kaveck1 par hypothèse surn0. La propositionP(n1)est fausse mais par définition den1, la proposition

P(n11)est vraie. Or par hypothèse, l"implicationP(n11))P(n1)est vraie donc la propositionP(n1)est vraie ce qui

entraîne une contradiction.1. Giuseppe Peano (1858-1932), mathématicien italien. 1 Le même procédé de preuve permet de montrer le résultat

Théorème 1.1.3(Récurrence forte).Soit P(n)une proposition dépendant d"un entier naturel n.

S"il existe un entier n

0tel que

la pr opositionP (n0)est vraie, pour tout entier n n0, la proposition "(8p2 fn0;:::;ngP(p)))P(n+1)" est vraie alors, pour tout entier nn0, la proposition P(n)est vraie.

!Pour démontrer qu"une propriété dépendant d"un entiernest vraie pour tous les entiers supérieurs à un entiern0on

effectue le raisonnement suivant : 1. (initialisation de la récurence) on vérifie la propriété pour n=n0 2.

(h ypothèsede récurence) on suppose que pour n>n0, la propriété est vraie pour toutk2 fn0;:::;n1g.

3. On prouv ela propriété au rang nen utilisant l"hypothèse de récurence. 4.

(conclusion) On conclut que la propriété est vraie pour tout nn0par le principe de récurence.

1.2 Ensembles finis, infinis, notion de cardinal

1.2.1 Ensembles finis

On note[[1;n]]l"ensemble des entiers naturels compris entre 1 etn. On rappelle les résultats :

Théorème 1.2.1.Soit p et n deux entiers.

1. Il e xisteune injection de [[1;p]]dans[[1;n]]si et seulement si pn. 2. Il e xisteune surjection de [[1;p]]dans[[1;n]]si et seulement si pn. 3. Il e xisteune bijection de [[1;p]]dans[[1;n]]si et seulement si p=n. 4.

Si n >0toute injection de[[1;n]]est bijective.

5.

T outesurjection de [[1;n]]est bijective.

Définition 1.2.2(Ensemble fini et cardinal).Un ensembleEest ditfinis"il existe un entiernet une bijection de[[1;n]]

dansE. Par le théorème précédent cet entiernest unique et on l"appellecardinaldeE. On le note CardE. Le cardinal de

l"ensemble vide est 0. Le théorème précédent a pour corollaire Corollaire 1.2.3.Soit E et F deux ensembles finis. 1. Il e xisteune injection de E dans F si et seulement si Car dECardF. 2. Il e xisteune surjection de E dans F si et seulement si Car dECardF. 3. Il e xisteune bijection de E dans F si et seulement si Car dE=CardF. 4. Si Car dE=CardF6=0alors toute injection de E dans F est bijective. 5. Si Car dE=CardF alors toute surjection de E dans F est bijective.

1.2.2 Ensemble infini

Définition 1.2.4(Ensemble infini, cardinal).Un ensemble estinfinis"il n"est pas fini. On étend aux ensembles infinis la

notion de cardinal : Deux ensemblesEetFont le mêmecardinalsi et seulement si il existe une bijection deEsurF. La

notion de cardinal est dûe à Cantor 2.

Remarque 1.2.5.La relation "il existe une bijection deEsurF" est une relation d"équivalence. Intuitivement on peut

considérer les cardinaux comme les classes d"équivalence pour cette relation.2. Georg Cantor (1845-1918), mathématicien allemand.

2

Définition 1.2.6(Opérations et relations sur les cardinaux).On considère les opérations suivantes :

CardA+CardB=Card(Af0g[Bf1g):

CardA:CardB=CardAB:

On pose CardACardBs"il existe une injection deAdansB.

Remarque 1.2.7.Afin de vérifier que cette définition a un sens il faut montrer que si CardA=CardA0et CardB=CardB0

alors

Card(Af0g[Bf1g) =CardA0f0g[B0f1g

et

CardAB=CardA0B0:

On vérifie cela en construisant les bijections adéquates, exercice! On admet que la relationest une relation d"ordre total sur les cardinaux3

Exemple 1.2.8.NotonsIl"ensemble des nombres entiers impairs. Le cardinal deIest égal au cardinal deN. En effet on

peut considérer l"application F:N!I n7!2n+1:

Cette application est surjective par définition deIet l"on vérifie immédiatement l"injectivité. Elle est donc bijective.

Exemple 1.2.9.Les ensemblesN,Z,Qont le même cardinal.

Exemple 1.2.10.Les ensemblesR,C,Rnpour toutn1 ont le même cardinal. On dit qu"ils ont lapuissance du continu.

Les ensemblesNetRn"ont pas le même cardinal (diagonale de Cantor).

L"hypothèse du continuformulée par Cantor, spécifie qu"il n"existe pas d"ensemble ayant un cardinal à la fois strictement

plus grand que celui des entiers et strictement plus petit que celui des réels.

SiEetFsont deux ensembles infinisayant même cardinal toute injection ou toute surjection n"est pas une bijection!

Définition 1.2.11(Ensemble dénombrable).Un ensemble est ditdénombrables"il est en bijection avec une partie deN.

on déduit de la définition :

Proposition 1.2.12.Un ensemble dénombrable est fini ou infini. Dans ce dernier cas son cardinal est celui deN.

1.3 Dénombrement

Dans tout ce qui suit les ensembles considérés sont finis et l"on considèrera la définition de cardinal énoncé en 1.2.4.

1.3.1 Opération sur les cardinaux d"ensembles finis

On déduit directement du corollaire 1.2.3 la proposition suivante :

Proposition 1.3.1(Partie d"un ensemble fini).Soit E un ensemble fini et A une partie de E. Nécessairement A est finie et

son cardinal vérifie CardACardE.

Proposition 1.3.2(Cardinal d"une réunion disjointe).Soit E et F deux ensembles finis disjoints. La réunion E[F est fini et

son cardinal vérifie

CardE[F=CardE+CardF:3. L"antisymétrie constitue le théorème de Cantor-Bernstein : s"il existe une injection deEdansFet une injection deFdansEalors il existe une

bijection deEdansF. Le fait que l"ordre soit total résulte de l"axiome du choix. 3

Démonstration.L"ensembleEest fini donc en bijection avec l"ensemble[[1;CardE]]. NotonsFEcette bijection. L"ensemble

Fest fini donc en bijection avec l"ensemble[[1;CardF]]. NotonsFFcette bijection. On considère l"application

F

E[F:E[F![[1;CardE+CardF]]

e2E7!FE(e) f2F7!FF(f)+CardE:

Remarquons que cette application est bien définie carEetFsont disjoints. En effet siEetFne sont pas disjoints alors

il existea2E\Fet en ce cas on a la contradiction suivante

CardE

Montrons que cette application est injective. Soitgethdeux éléments deE[Ftels queFE[F(g) =FE[F(h). Sigeth

appartiennent àEalors F

E(g) =FE[F(g) =FE[F(h) =FE(h)

orFEest une bijection doncg=h. On fait le même raisonnement sigethappartiennent àF. Supposons quegappartient à

EethàFalors nous avons

F

E(g)CardE Ce cas est donc à exclure carFE[F(g)6=FE[F(h). Cela prouve donc l"injectivité.

Montrons que cette application est surjective. Soitk2[[1;CardE+CardF]]. SikCardEalors par surjectivité deFE

il existee2Etel queFE(e) =k. De même si CardE

surjectivité.Proposition 1.3.3(Cardinal d"une réunion quelconque).Soit E et F deux ensembles finis. La réunion E[F est finie et son

cardinal vérifie

CardE[F=CardE+CardFCardE\F:

Démonstration.Par la proposition précédente on obtient les égalités

CardE=Card(EnE\F)+CardE\F;

CardF=Card(FnE\F)+CardE\F;

grâce aux décompositions

E=En(E\F)t(E\F)etF=Fn(E\F)t(E\F):

Par la décomposition

E[F= (En(E\F))t(Fn(E\F))t(E\F);

et l"usage de la proposition précédente on a

CardE[F= (CardECardE\F)+(CardFCardE\F)+CardE\F

=CardE+CardFCardE\F:Plus généralement :

Proposition 1.3.4(Formule du crible).Soit E un ensemble fini, I l"ensemblef1;:::;nget(Ai)i2Iune famille de parties de E.

Le cardinal de l"union se décompose alors comme suit : Card i2IA i! =nå i=1(1)i+1å

JI;Card(J)=iCard \

j2JA j! Exemple 1.3.5.SoitA,BetCtrois parties deEon a alors Card(A[B[C) =Card(A)+Card(B)+Card(C)Card(A\B)Card(A\C)Card(B\C)+Card(A\B\C): 4 Démonstration.On fait la preuve par récurence surn. Dans le casn=2, nous avons déjà démontré la formule du crible. Supposons le résultat vrai pournparties et montrons le pourn+1 partiesA0;:::;AndeE. Considérons les deux partiesA0etSni=1Ainous obtenons Card A 0[n[ i=1A i! =CardA0+Card n[ i=1A i! Card A 0\n[ i=1A i!

Remarquons que

A 0\n[ i=1A i=n[ i=1(A0\Ai): En appliquant l"hypothèse de récurrence, en notantI=f1;:::;ngnous obtenons Card A 0[n[ i=1A i! =CardA0+nå i=1(1)i+1å

JI;Card(J)=iCard \

j2JA j! nå i=1(1)i+1å

JI;Card(J)=iCard

A 0\\ j2JA j! c"est à dire Card A 0[n[ i=1A i! =n+1å i=1(1)i+1å

Jf0g[I;Card(J)=iCard \

j2JA j! :Proposition 1.3.6(Cardinal d"un produit).Si E et F sont deux ensembles finis alors EF est fini et

CardEF=CardE:CardF:

Démonstration.Intuitivement on peut considérer l"ensembleEFcomme un tableau ayant CardElignes et CardFco-

lonnes. On constate donc que le nombre d"éléments deEFest le produit des cardinaux. Numérotant les éléments du

tableau de gauche à droite et de haut en bas, la lecture du tableau fournit alors une bijection explicite :

F

EF:EF![[1;CardE:CardF]]

(e;f)7!(FE(e)1)CardF+FF(f):

oùFE:E![[1;CardE]]etFF:F![[1;CardF[]sont des bijections.Proposition 1.3.7(Cardinal ensembles des applications).Si E et F sont deux ensembles finis alors l"ensemble des applica-

tions de E dans F, noté F

E, est fini et

Card(FE) = (CardF)CardE:

quotesdbs_dbs10.pdfusesText_16

[PDF] exercices dénombrement première pdf

[PDF] probabilité dénombrement cours

[PDF] exercices dénombrement mpsi

[PDF] formule dénombrement microbiologique

[PDF] p uplet

[PDF] p liste arrangement combinaison

[PDF] n-uplet definition

[PDF] formule arrangement

[PDF] p liste exercice

[PDF] arrangement combinaison permutation

[PDF] m=m/na

[PDF] que veut dire ci après dénommé

[PDF] ci après dénommé le bailleur

[PDF] ci-après dénommé définition

[PDF] ci-après désignée