Cours de mathématiques - 1ère année de CPGE économique et commerciale, voie ECS, Dénombrement

De
Publié par

Ce cours complet de mathématiques est composé de 21 chapitres : (0) Sommaire (1) Ensembles (2) Applications et Fonctions (3) Sommes et Produits (4) Polynômes (5) Suites numériques (6) Séries numériques (7) Limites et continuité (8) Calcul différentiel (9) Intégration (10) Développements limités (11) Fonctions de deux variables (12) Dénombrement (13) Espaces probabilisés (14) Variables aléatoires discrètes (15) Opérations sur les variables aléatoires discrètes (16) Statistique descriptive (17) Systèmes d’équations linéaires (18) Matrices (19) Espaces vectoriels (20) Applications linéaires (21) Réduction
Publié le : samedi 1 janvier 2011
Lecture(s) : 314
Licence : En savoir +
Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
Nombre de pages : 8
Voir plus Voir moins
Dénombrement
- 1 -
DENOMBREMENT
ECS 1
 I - Généralités  1) Cardinal d’un ensemble Exemple On : récite l’alphabet toujours de la même manière : on définit une application de {1,...,26} dans l’ensembleE des lettres et ainsi, on compte toutes les lettres, sans jamais les compter deux fois. C’est une bijection car toute lettre possède un numéro (antécédent) et un seul. Remarque : Sinetpsont des entiers naturels non nuls, il existe une bijection de1,n dans1,psi et seulement sin p. Définition : SoitEun ensemble non vide.  S’il existe un entiern bijection de* et une1,ndansE, alors cet entiernest unique. On dira queE Cardest un ensemble fini et que :E n.  S’il existe une bijection de* dansE, on dira queE un ensemble infini est dénombrable.  Sinon, on dira queEest un ensemble infini non dénombrable. Par convention, est un ensemble fini et Card( .) 0 Le cardinal d’un ensemble fini est le nombre de ses éléments. On définit aussi le cardinal d’un ensemble infini, mais c’est beaucoup plus compliqué. Exemples: L’ensemble des nombres impairs etsont infinis dénombrables.  et [0,1] sont infinis non dénombrables. 2) Propriétés Théorème : SiE etF deux ensembles finis tels que sontE, alors Card(E) Card(F Si) .Eet Card(E) Card(F) , alorsE. Pour montrer que deux ensembles sont égaux, il suffit de montrer que l’un est inclus dans l’autre et qu’ils ont le même nombre d’éléments. Théorème : SiAetBsont deux parties d’un ensemble finiE, alors : Card(AB) Card(A) Card(B) Card(A B) . En particulier siA B(AetB Card(disjointes) :AB) Card(A) Card(B) . Evident siA B: on compte les éléments deApuis ceux deBet on additionne. C’est le principe du berger : il compte les moutons noirs, puis les moutons blancs ! SiA B, en comptant les éléments deA, puis ceux deB, on compte deux fois les éléments communs. Il faut donc enlever Card(A B) . Plus précisément, on se ramène au premier cas :AB AB' avecB'B A( doncAetB' disjointes). La généralisation est la formule de Poincaré (ou du crible) qui permet de calculer le cardinal de la réunion denparties. On ne la démontrera que pourn3 : ABC(AB)C. Donc : Card(ABC) Card(AB) Card(C) Card[(AB)C] . Or : (AB)C(A C)(B C) . Donc : Card[(AB)C] Card(A C) Card(B C) Card[(A C) (B C)] . Et (A C) (B C)A B C. En remplaçant, on obtient :
Card(ABC) Card(A) Card(B) Card(C) Card(A B) Card(B C) Card(AC)Card(ABC) Pourn avec une démonstration analogue, on obtient :4 ,
- 2 -
Dénombrement ECS 1 Card(ABCD) Card(A) Card(B) Card(C) Card(D) Card(A B) Card(AC)Card(AD)Card(BC)Card(BD) Card(CD)Card(ABC)Card(ABD) Card(ACD)Card(BCD)Card(ABCD) La formule générale est très compliquée : Formule du crible ou de Poincaré : Cardin1Aikn1(1)k11i1...iknCard(Ai1...Aik) Elle a été rappelée dans l’épreuve ESSEC 2004 ! Théorème : SiA1,A2,…,Anest une partition d’un ensembleE, alors : Card(E)Card(A1)Card(A2)...Card(An) En effet, si les parties sont deux à deux disjointes, toutes les intersections sont vides. Donc : Card(A1...An)Card(A1)...Card(An) . Le cas le plus simple est celui deAetAcarAA EetAA. Théorème : SiAest une partie d’un ensemble finiE, Card(A)Card(E)Card(A) . SiEetFsont deux ensembles, on noteEl’ensemble de tous les couples (x,y) où xest un élément deEetyun élément deF. Théorème : SiEetFsont finis,Eest fini et Card(E F) Card(E) Card(F) . Si Card(E)net Card(F)p, on peut représenterEsous la forme d’un tableau ànlignes etpcolonnes, doncnpcases. Plus généralement : Card(E1...Ek)Card(E1)...Card(Ek) Et en particulier siE1...EkE: Card(Ek)[Card(E)]k  3) Propriétés liées aux applications On se place dans le cas où les ensemblesEetF sont finis, mais certaines considérés propriétés restent vraies siFne l’est pas. Théorème : Sif est une application d’un ensemble finiE dans un ensemble finiF, alors Cardf(E) CardEet Cardf(E) CardF. De plus :  fest injective si et seulement si Cardf(E) CardE.  fest surjective si et seulement si Cardf(E) CardF. En effet,f(E l’ensemble des images des éléments de) estE. Donc il n’y a pas plus d’images que d’antécédents. f est injective si et seulement si tous les éléments distincts deE des images ont distinctes, donc si et seulement siEetf(E le même nombre d’éléments.) ont f surjective si et seulement si tout élément de estF au moins un antécédent, possède donc si et seulement sif(E)F.
II – Dénombrement Définition : Dénombrer un ensemble fini, c’est compter ses éléments, c’est à dire calculer son cardinal. S’il existe une bijection entre deux ensembles finis, ils seront en bijection avec la même partie1,n de* . Donc ils auront le même cardinal. En utilisant cette propriété, on peut remplacer le dénombrement d’un ensemble compliqué par le dénombrement d’un ensemble plus simple ou déjà dénombré. On a donc essayé de déterminer des situations modèles pour économiser les calculs et les raisonnements.
Dénombrement - 3 - ECS 1 1) Principes de dénombrement C’est un problème d’organisation : on utilise souvent des arbres ou des tableaux ou tout autre mode de représentation visuelle. Exemple 1 combien dessine-t-on de carrés ? , construisant un quadrillage: En 4 4 On compte les carrés de côté 1 (il y en a 16), puis les carrés de côté 2 (il y en a 9), puis les carrés de côté 3 (il y en a 4), puis les carrés de côté 4 (il y en a 1). Donc :N16 9 4 1 30 . On a réalisé une partition de l’ensemble des carrés. Principe additif : On réalise une partition de l’ensemble à dénombrer, on calcule les cardinaux de chaque partie et on additionne pour calculer le cardinal de l’ensemble. Exemple 2: Un anagramme de HEC est un mot de trois lettres formé avec H, E et C. Pour dénombrer les anagrammes de HEC, on a deux méthodes : (1) O p dans l’ordre les trois places t _ _ _ n rem li vides : - Pour la première place, on choisit une lettre parmi H, E et C : il y a 3 possibilités. -  pour :on choisit une lettre parmi les deux restantesPour la deuxième place, chaque choix de la première lettre, on a 2 possibilités pour la deuxième (ce ne sont pas les mêmes). - Pour la troisième place, il ne reste plus qu’une lettre. (2) des lettres H, E et C :On choisit les places - Pour la lettre H, il y a 3 places possibles. -  pour chaque choix de laPour la lettre E, il ne reste plus que 2 places vides : place de H, il reste 2 possibilités pour E (ce ne sont pas les mêmes). - Pour la lettre C, il ne reste plus qu’une seule place vide. Dans les deux cas, on construit un arbre et on obtientN anagrammes. 63 2 1 Dans le cas des anagrammes de ESSEC, on a toujours 3 lettres, mais on doit remplir 5 places vides en répétant deux fois E et deux fois S. (1) On remplit dans l’ordre les 5 places vides : _ _ _ _ _ On construit ici un arbre dissymétrique difficile à dénombrer. (2) en même temps les places des deuxOn choisit les places des lettres en choisissant E et des deux S, sinon on compte plusieurs fois les mêmes mots : - Pour la lettre C, il y a 5 places possibles. - Pour les deux lettres E, il reste 4 places vides et on doit en choisir 2 : il y a 6 manières de les placer (on les compte à la main).   : il y a une seulePour les deux lettres S, il ne reste plus que 2 places vides -manière de les placer. Là aussi on construit un arbre et on obtient :N . 305 6 1 Principe multiplicatif : On décompose le problème enk qui comportent étapes chacune un nombreni indépendant des résultats des autres étapes. Alors le d’issues nombre total d’issues du problème estN n1...nk. C’est le nombre qui est indépendant, pas les issues. Dans la plupart des cas, on imagine l’arbre sans pouvoir le dessiner. Exemple 3y a-t-il de numéros d’immatriculation de voitures dans un Combien  : département de province? (un nombre entre 1 et 9999 et deux lettres autres que I et O). On construit un arbre avec trois choix successifs :N .9999 24 24 2) Dénombrement desp-listes avec répétition  Exemple 1: Un code est formé de trois lettres. Combien peut-on former au maximum de codes différents ? On a 3 choix successifs, donc un arbre à 3 étapes et pour chaque étape, il y a 26 possibilités. Donc :N262626263.
Dénombrement - 4 - ECS 1 Définition : Soientpetndeux entiers naturels non nuls. On appellep-liste d’éléments d’ensembleEtout élément deEp (c’est-à-dire tout élément de la forme, e1,...,ep) où tous leseisont éléments deE. On dit aussip-uplet ou mot de longueurp. Une 2-liste est un couple et une 3-liste est un triplet. Théorème : Sip Cardest un entier naturel non nul et siE n, alors le nombre dep-listes deEestnp. C’est le cardinal deEpque l’on a déjà calculé. Exemple 2 jette deux fois de suite un dé. Quel est le nombre de résultats On : possibles ? On obtient des couples (x,y 1) avecx 16 ety6 . Donc :N62. On peut l’interpréter différemment suivant les exemples. Théorème : Le nombre de tirages successifs avec remise depéléments parminestnp. Exemple 3: Une urne contient 10 jetons numérotés de 0 à 9. On tire successivement avec remise trois jetons. Quel est le nombre de résultats possibles ? Pour chaque jeton, il y a 10 numéros possibles. Donc :N103. Exemple 4 Une urne  :contient 5 boules vertes, 3 rouges et 1 blanche. On tire successivement avec remise quatre boules. Combien peut-on obtenir de répartitions de couleurs différentes ? Pour chaque boule, il y a 3 couleurs possibles. Donc :N34. Théorème : Le nombre d’applications d’un ensemble àpéléments dans un ensemble à néléments estnp. En effet, choisir une application revient à choisir dans l’ensemble d’arrivée lesp images des éléments de l’ensemble de départ : pour chacune, il y an .s possibilité Exemple 5 personnes montent dans un ascenseur qui dessert 5 étages. Combien y: 3 a-t-il de répartitions possibles des personnes dans les étages ? A chaque personne, on associe le numéro de l’étage où elle descend. Le problème revient donc à tirer successivement avec remise 3 numéros parmi 5. Donc :N53. Mais si ce sont 3 voitures qui se garent dans 5 places de parking ? 3) Dénombrement desp-listes sans répétit o i n Exemple 1de manières différentes peut-on garer 3 voitures dans 5 places: De combien de parking ? Elles ne peuvent pas se mettre sur la même place. Donc les numéros tirés doivent être différents. On a trois choix successifs : pour la première voiture, il y a 5 places vides, pour la deuxième, il n’en reste que 4 et pour la dernière, il en reste 3. Donc :N .5 4 3 Définition : Sip un entier naturel non nul, on appelle estp-liste sans répétition ou arrangement d’ordrepd’un ensembleEtoutep-liste formée d’éléments distincts deE. Comme pour les voitures, souvent, c’est le bon sens qui permet d’affirmer que les éléments sont distincts. Théorème : Sip Cardest un entier naturel non nul et siE n (n alors le nombre0) , d’arrangements d’ordrepd’éléments deEest : Apn0 sipn        Apnn(n1)...(np1)(n!) ! isp n. np Démonstration : Dans le caspn, on ne trouvera paspéléments distincts. Dans le casp n, on utilise le principe multiplicatif et on construit un arbre : Choix du 1erélément :npossibilités. Choix du 2ème élément : (n (on a déjà retiré 1 élément).1) possibilités Et ainsi de suite...
Dénombrement
5 - -
ECS 1
Choix dupème : élémentn(p1)n p1 possibilités (on a déjà retirép1 éléments). Théorème : Le nombre de tirages successifs sans remise depéléments parminestApn. Exemple 2 Une :1 à 8. Quel est le nombre de urne contient 8 jetons numérotés de manières de tirer 3 jetons successivement sans remise ? On obtient des triplets de numéros distincts puisqu’on ne remet pas les jetons tirés.     Donc :NA83 .8 7 6 336 Exemple 3une course de 12 chevaux, calculer le nombre de tiercés possibles ?: Dans On obtient des triplets de numéros distincts. DoncNA2131211101320 . Théorème : Le nombre d’applications injectives d’un ensemble àp éléments dans un ensemble ànéléments estApn. En effet, choisir une application injective revient à choisir dans l’ensemble d’arrivée lespimages distinctes des éléments de l’ensemble de départ. Exemple 1: A chaque voiture, on associe sa place de parking. 4) Dénombrement des permutations d’un ensemble Définition : Sinest un entier naturel non nul, on appelle permutation d’un ensemble Eànéléments toute bijection deEdansE. Exemple 1: Une table comporte 5 places numérotées. Calculer le nombre de manières de disposer les 5 invités autour de cette table ? Disposer les invités revient à attribuer à chacun un numéro de place. C’est une bijection car tous les invités sont placés à des places différentes, et toutes les places sont occupées. On peut remarquer qu’il suffit que ce soit une injection. Une disposition est donc un arrangement d’ordre 5 de l’ensemble des personnes. Donc NA5554321120 . Plus généralement, une permutation d’un ensembleEànéléments est un arrangement d’ordrende E car CardECardf(E) CardF. Théorème : Si CardE n (n le nombre de permutations de0) ,Eest :n!. Exemples: 1! 2 , 1, 2! ,... 720 6! , 4! , 6 3! 120 5! , 24 Propriétés : (n1)! (n1) (n 1.!) et 0! par convention : Exemple 2 . 24 4!: Le nombre d’anagrammes de MAIN est Théorème : Le nombre de manières d’ordonnernéléments distincts estn! .
5) Dénombrement des parties d’un ensemble Exemple 1 la course de 12 chevaux, il y a évidemment 1 seul tiercé gagnant.: Dans Mais combien va-t-il y avoir de tiercés avec les chevaux gagnants ?N .3! 6 Il y a donc 6 tiercés qui vont gagner soit dans l’ordre, soit dans le désordre. On a vu que le nombre total de tiercés possibles estNA2311211101320 . 3 Donc le nombre de tiercés non ordonnés estA31!2 C’est le nombre de parties à 3220 . éléments dans l’ensemble des 12 chevaux. Définition : Sipest un entier naturel, on appelle combinaison d’ordrepd’un ensemble Etoute partie àpéléments de l’ensembleE. Exemple 2 : (on coche 6 numérosy a-t-il de grilles de loto différentes ? Combien parmi 49). Mais l’ordre dans lequel on coche ces numéros n’a pas d’importance. Le nombre de manières de cocher 6 numéros distincts sur la grille est :A469.
Dénombrement
- 6 -
ECS 1
Donc 6! manières donnent la même grille. Il y a doncA646!9grilles différentes. Théorème : Sip Card un entier naturel et si estE n (n0) , le nombre de combinaisons d’ordrepdeEest : np!   np0 sipnppAnp!(nnpis  )!p n. ! Démonstration : Il y aApn arrangements d’ordrep. Mais chaque partie àp éléments correspond àp! arrang Donc . renApn ements d’ordppp  .! Remarque : La formule est même vraie sip il n’y a qu’une seule partie à 00 car élément, c’est. En termes de tirages, les parties correspondent à des tirages sans ordre, donc simultanés. Théorème : Le nombre de tirages simultanés depéléments parminestnp. Par contre, on ne peut pas interpréter en termes d’applications. Exemple 3: Dans un jeu de 32 cartes, calculer : 1) le nombre de mains de 5 cartes. 2) le nombre de mains de 5 cartes avec 2 cœurs et 3 piques. 3) le nombre de mains de 5 cartes avec 3 trèfles. 4) mains de 5 cartes avec 2 rois et 2 dames.le nombre de 5) le nombre de mains de 5 cartes avec 2 rois et 2 cœurs. 6) le nombre de mains de 5 cartes avec au moins un valet. 1) Une main de 5 cartes est une combinaison d’ordre 5 dans l’ensemble des 32 cartes. DN67310223 onc15. 2) On doit choisir 2 cœurs parmi 8, puis 3 piques parmi 8. Donc, on obtient : . N228381 568 3) On doit choisir 3 trèfles parmi 8, puis 2 cartes complémentaires parmi les 32 8 24 cartes autres que le trèfle. Donc, on obtient :N383242 .15 456 4) On doit choisir 2 rois parmi 4, puis 2 dames parmi 4, puis 1 carte complémentaire parmi les 32 8 24 cartes autres que rois et dames. Donc, on obtient : N4424936 . 4 22 2 9 5) Cette fois, le problème se complique car les choix des rois et des cœurs ne sont pas indépendants puisqu’il peut y avoir le roi de cœur. On compte d’abord les mains avec le roi de cœur :N'513117212 le roi de cœur, puis un4410 , car on choisit roi parmi les 3 autres rois, puis un cœur parmi les 7 autres cœurs, puis 2 cartes complémentaires parmi les 32 11 21 cartes autres que les rois et les cœurs), puis les mains sans leN"37211323 , car on choisit 2 rois roi de cœur :52 2 1 parmi les 3 rois autres que le roi de cœur, puis un cœur parmi les 7 cœurs autres que le
Dénombrement
- 7 -  
ECS 1
roi de cœur, puis 1 carte complémentaire parmi les 32 11 21 cartes autres que les ' " rois et les cœurs). DoncN5N5N5 .5 733 6) Il y a deux méthodes : - Soit on compte les mains avec 1 valet et 4 cartes complémentaires prises parmi les 32 4 28 cartes autres que les valets, puis les mains avec 2 valets et 3 autres cartes, puis les mains avec 3 valet et 2 autres cartes, puis les mains avec 4 valets et 1 autre 8 4 28carte. Donc :N64142842283342241 103 096 .             - Soit on compte toutes les mains de 5 cartes, et on enlève le nombre de mains de 5 cartes sans valet, donc prises parmi 28. DoncN6532582103 096 .
De manière générale, lorsque l’on doit dénombrer les éléments d’un ensemble, ce que l’on sait calculer, c’est « exactement … ». Lorsque l’on doit dénombrer « au plus … » ou « au moins … », il faut décomposer par partition. Lorsque l’on doit dénombrer « au moins … », il y a une autre méthode : dénombrer le complémentaire. On choisit la méthode qui engendre le moins de calculs. 6) Retour sur la formule du binôme de Newton Formulea bnnbnnan kbk du binôme de Newton : ()nk0kak n kk0k. On retrouve les coefficients du binôme. En effet, dans le développement de (a b)n(ab)(ab)...(ab tous les termes) , sont constitués den lettres ordonnées égales àa oub que l’on réordonne ensuite par commutativité. Le coefficient du termeakbn kest donc le nombre d’anagrammes de a....a b....b, donc le nombre de manières de choisir lesk places desa parmi lesn kfoisnkfois places, doncn. kLes propriétés de ces coefficients peuvent se justifier de manière ensembliste. Propriétés :npnpn     pn1pnpn1 si 1p n Démonstration : La première est vraie car il y a autant de parties àp éléments que de leurs complémentaires à (n p) éléments. La deuxième se démontre en fixant un élémenta deE en posant etFEa. Si CardE n1, alors CardF n. On notep(E des parties à) l’ensemblepéléments deEet on réalise une partition de cet ensemble :  les parties qui contiennentaet donc (p1) éléments deF. Leur ensemble est en bijection avecp1(F) . Il y en a doncpn1.  les parties qui ne contiennent pasa, donc qui contiennentp de élémentsF. Leur ensemble estp(F) . Il y en a doncpn.
Dénombrement
- 8 -
ECS 1
Donc :n1nn. p p p1nn De plus, on sait que :k0k2n. Cela revient à compter toutes les parties deE. Conséquence : Si CardE n, alors Card(E)2n. Une autre propriété sera utile en probabilités. Vandermonde :np q p q Formule dek0knkn. Démonstration : Une urne contientpboules blanches etqboules noires. Le nombre de tirages simultanés denboules est :npq. Mais on peut définir une partition de ces a tirages suivant le nombre de boules blanches obtenues. Il ypkknqtirages qui contiennentkblanches et (n k 0) noires pourkn.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.