BURHAN.

Dénombrement : Résumé de cours de Mathématiques 1BAC Sciences Économiques et Gestion

Dénombrement : résumé de maths 1BAC SEG, avec les points essentiels, les formules et les méthodes à retenir pour réviser avant un contrôle. Pour les élèves de 1BAC Sciences Économiques et Gestion, option française (BIOF).

Ensembles finis et cardinal

RemarquePetit rappel de vocabulaire

A∩BA \cap B (intersection) : les éléments communs à AA et à BB. A∪BA \cup B (réunion) : les éléments qui sont dans AA, dans BB, ou dans les deux.

AA et BB sont disjoints si A∩B=∅A \cap B = \varnothing. Le complémentaire A‾\overline{A} de AA dans EE regroupe les éléments de EE qui ne sont pas dans AA.

Le principe additif, ci-dessous, et le principe général du dénombrement, à la section suivante, sont admis : tu les cites sans les prouver.

DéfinitionEnsemble fini, cardinal

Un ensemble EE est fini s'il est vide, ou s'il existe un entier naturel non nul nn tel que l'on puisse numéroter ses éléments de 11 à nn, chaque élément recevant un seul numéro et chaque numéro étant employé une seule fois.

L'entier nn s'appelle alors le cardinal de EE : c'est le nombre d'éléments de EE. On le note card⁡(E)\operatorname{card}(E). Par convention, card⁡(∅)=0\operatorname{card}(\varnothing) = 0.

PropriétéPrincipe additif

Soit AA et BB deux ensembles finis disjoints, c'est-à-dire tels que A∩B=∅A \cap B = \varnothing. Alors card⁡(A∪B)=card⁡(A)+card⁡(B).\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B). Plus généralement, si A1A_1, A2A_2, ..., ApA_p sont des ensembles finis deux à deux disjoints, alors card⁡(A1∪A2∪⋯∪Ap)=card⁡(A1)+card⁡(A2)+⋯+card⁡(Ap)\operatorname{card}(A_1 \cup A_2 \cup \dots \cup A_p) = \operatorname{card}(A_1) + \operatorname{card}(A_2) + \dots + \operatorname{card}(A_p).

PropriétéCardinal du complémentaire et de la réunion

Soit EE un ensemble fini, et AA et BB deux parties de EE.

  • Le complémentaire A‾\overline{A} de AA dans EE (ensemble des éléments de EE qui n'appartiennent pas à AA) vérifie card⁡(A‾)=card⁡(E)−card⁡(A).\operatorname{card}(\overline{A}) = \operatorname{card}(E) - \operatorname{card}(A).
  • La réunion de AA et BB vérifie card⁡(A∪B)=card⁡(A)+card⁡(B)−card⁡(A∩B).\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B) - \operatorname{card}(A \cap B).

Exemple

Une épicerie fine référence 3030 produits (données fictives). Parmi eux, 1212 sont bio (ensemble AA), 99 sont en promotion (ensemble BB), et 44 sont à la fois bio et en promotion.

  • Bio ou en promotion : card⁡(A∪B)=12+9−4=17\operatorname{card}(A \cup B) = 12 + 9 - 4 = 17.
  • Ni bio ni en promotion : c'est le complémentaire de A∪BA \cup B, donc 30−17=1330 - 17 = 13 produits.
  • Bio mais pas en promotion : 12−4=812 - 4 = 8 produits.

AttentionNe compte pas deux fois l'intersection

Dans l'épicerie, 12+9=2112 + 9 = 21 dépasse le vrai nombre 1717 : les 44 produits bio en promotion sont comptés deux fois. On additionne directement les cardinaux seulement pour des ensembles disjoints. Sinon, on retire card⁡(A∩B)\operatorname{card}(A \cap B).

MéthodePasser par le contraire, ou découper en cas

  1. Repère les mots « au moins » : compte d'abord le contraire, « aucun », puis retire-le du total.
  2. Découpe une situation à plusieurs cas en cas qui ne se recouvrent pas : « exactement 0 », « exactement 1 », et ainsi de suite.
  3. Additionne les nombres trouvés, grâce au principe additif.
  4. Contrôle : chaque situation doit tomber dans un cas, et dans un seul.

Principe général, arbre de choix, p-listes

PropriétéPrincipe général du dénombrement

On considère une situation qui se réalise par pp choix successifs (p≥2p \geq 2). On suppose que :

  • le premier choix peut se faire de n1n_1 façons ;
  • pour chaque façon de faire le premier choix, le deuxième peut se faire de n2n_2 façons ;
  • et ainsi de suite : pour chaque façon de faire les choix précédents, le pp-ième choix peut se faire de npn_p façons.

Alors le nombre total de façons de réaliser la situation est n1×n2×⋯×np.n_1 \times n_2 \times \dots \times n_p.

Exemple

La cantine d'une entreprise propose 33 entrées, 44 plats et 22 desserts (exemple fictif). Arbre de choix : premier choix, l'entrée (33 branches) ; pour chaque entrée, le plat (44 branches) ; pour chaque plat, le dessert (22 branches). Un menu est un chemin de l'arbre : il y a 3×4×2=243 \times 4 \times 2 = 24 menus. Dessine les premières branches sur ton cahier pour le vérifier.

Arbre de choix horizontal à trois niveaux. De la racine partent les trois entrées E_1, E_2 et E_3. De chaque entrée repartent quatre plats, P_1 à P_4. De chaque plat repartent deux desserts, D_1 et D_2. Un menu se lit en suivant un chemin de la racine jusqu'à un dessert ; la colonne de droite aligne 3 fois 4 fois 2, c'est-à-dire 24 desserts possibles.

Tous les menus de la cantine : trois entrées E, quatre plats P sous chacune, deux desserts D sous chaque plat, soit 24 bouts de branches.

MéthodeCompter avec un arbre de choix

  1. Découpe la situation en une suite de choix, faits dans un ordre que tu fixes.
  2. Esquisse l'arbre : une branche pour chaque façon de faire un choix.
  3. Vérifie que chaque choix a le même nombre de branches, quel que soit le chemin déjà suivi.
  4. Multiplie ces nombres si c'est le cas. Sinon, compte les chemins sous chaque branche, puis additionne.

Exemple

Une marque de jus (exemple fictif) vend une bouteille en 44 parfums, une brique en 33 parfums et une canette en 22 parfums. Le nombre de parfums dépend du format : on ne peut pas multiplier. On compte les chemins branche par branche : 4+3+2=94 + 3 + 2 = 9 produits.

PropriétéCardinal d'un produit cartésien

Soit EE et FF deux ensembles finis. Le produit cartésien E×FE \times F est l'ensemble des couples (x,y)(x, y) tels que x∈Ex \in E et y∈Fy \in F. Alors card⁡(E×F)=card⁡(E)×card⁡(F).\operatorname{card}(E \times F) = \operatorname{card}(E) \times \operatorname{card}(F). Plus généralement, si EE a nn éléments et si pp est un entier naturel non nul, une pp-liste d'éléments de EE est une suite ordonnée (x1,x2,…,xp)(x_1, x_2, \dots, x_p) d'éléments de EE, distincts ou non. L'ensemble EpE^p des pp-listes d'éléments de EE vérifie card⁡(Ep)=np.\operatorname{card}(E^p) = n^p.

Exemple

Une tenue de travail associe une chemise parmi 44 et un pantalon parmi 33 (exemple fictif) : c'est un couple du produit cartésien, d'où 4×3=124 \times 3 = 12 tenues.

Un questionnaire de satisfaction a 55 questions, chacune à 33 réponses : oui, non, sans avis. Une fiche remplie est une 55-liste de l'ensemble des 33 réponses : il y a 35=2433^5 = 243 fiches possibles.

Arrangements et permutations

DéfinitionFactorielle, arrangement

Pour tout entier naturel non nul nn, la factorielle de nn est le nombre n!=1×2×⋯×nn! = 1 \times 2 \times \dots \times n. Par convention, 0!=10! = 1.

Soit EE un ensemble à nn éléments et pp un entier tel que 1≤p≤n1 \leq p \leq n. Un arrangement de pp éléments de EE est une pp-liste d'éléments de EE deux à deux distincts. Dans un arrangement, l'ordre compte et aucun élément n'est répété. Le nombre d'arrangements de pp éléments d'un ensemble à nn éléments se note AnpA_n^p.

PropriétéNombre d'arrangements

Soit nn et pp deux entiers naturels tels que 1≤p≤n1 \leq p \leq n. Alors Anp=n×(n−1)×⋯×(n−p+1)=n!(n−p)!.A_n^p = n \times (n - 1) \times \dots \times (n - p + 1) = \dfrac{n!}{(n - p)!}. Le premier produit compte pp facteurs.

Exemple

Neuf boutiques (exemple fictif) concourent pour la plus belle vitrine. Le palmarès nomme un gagnant, un deuxième et un troisième : l'ordre compte, et aucune boutique ne figure deux fois au palmarès. Un palmarès est donc un arrangement de 33 boutiques parmi les 99 boutiques : A93=9×8×7=504A_9^3 = 9 \times 8 \times 7 = 504 palmarès. Avec les factorielles : 9!6!=362 880720=504\dfrac{9!}{6!} = \dfrac{362\,880}{720} = 504.

PropriétéNombre de permutations

Soit EE un ensemble à nn éléments (n≥1n \geq 1). Une permutation de EE est un arrangement des nn éléments de EE : c'est une façon de ranger tous les éléments de EE dans un ordre. Le nombre de permutations de EE est n!.n!.

Exemple

Premières factorielles : 1!=11! = 1, 2!=22! = 2, 3!=63! = 6, 4!=244! = 24, 5!=1205! = 120, 6!=7206! = 720, 7!=50407! = 5040. Ranger 55 produits différents sur une étagère, c'est former une permutation de ces 55 produits : 5!=1205! = 120 rangements. Astuce de calcul : n!=n×(n−1)!n! = n \times (n - 1)!, par exemple 7!=7×720=50407! = 7 \times 720 = 5040.

AttentionZéro factorielle vaut un

0!=10! = 1, et non 00. Sans cette convention, la formule Anp=n!(n−p)!A_n^p = \dfrac{n!}{(n - p)!} ne marcherait pas pour p=np = n. Avec n=6n = 6 : A66=6!0!=7201=720=6!A_6^6 = \dfrac{6!}{0!} = \dfrac{720}{1} = 720 = 6!. Écrire 0!=00! = 0 ferait diviser par zéro.

Combinaisons

DéfinitionCombinaison

Soit EE un ensemble à nn éléments et pp un entier tel que 0≤p≤n0 \leq p \leq n. Une combinaison de pp éléments de EE est une partie de EE qui a pp éléments. Dans une combinaison, l'ordre ne compte pas et aucun élément n'est répété.

Le nombre de combinaisons de pp éléments d'un ensemble à nn éléments se note CnpC_n^p.

PropriétéNombre de combinaisons

Soit nn un entier naturel non nul et pp un entier tel que 0≤p≤n0 \leq p \leq n. Alors Cnp=n!p! (n−p)!.C_n^p = \dfrac{n!}{p!\,(n - p)!}. En particulier, pour 1≤p≤n1 \leq p \leq n, Cnp=Anpp!C_n^p = \dfrac{A_n^p}{p!}.

Exemple

Un service qualité choisit 44 produits parmi 1111 pour un test (exemple fictif). L'ordre ne compte pas et aucun produit n'est pris deux fois : c'est une combinaison. C114=11×10×9×84!=792024=330.C_{11}^{4} = \dfrac{11 \times 10 \times 9 \times 8}{4!} = \dfrac{7920}{24} = 330. Il y a donc 330330 échantillons possibles.

AttentionL'ordre compte-t-il ?

Dans une équipe fictive de 1212 personnes, désigner un chef et un adjoint donne A122=12×11=132A_{12}^{2} = 12 \times 11 = 132 choix : les deux postes sont différents. Désigner deux représentants au même rôle donne C122=1322=66C_{12}^{2} = \dfrac{132}{2} = 66 choix. On divise par 2!=22! = 2 seulement quand l'ordre ne compte pas.

Exemple

Un comité de 33 personnes est choisi dans un groupe fictif de 55 femmes et 66 hommes. En tout : C113=165C_{11}^{3} = 165 comités. Sans femme : C63=20C_6^3 = 20 comités. Avec au moins une femme, par le complémentaire : 165−20=145165 - 20 = 145 comités.

Attention« Au moins une » n'est pas « exactement une »

Dans le comité précédent, les choix à exactement une femme sont 5×C62=5×15=755 \times C_6^2 = 5 \times 15 = 75, et non 145145. Il manque les comités à deux femmes, C52×6=60C_5^2 \times 6 = 60, et à trois femmes, C53=10C_5^3 = 10. Le découpage complet redonne bien 75+60+10=14575 + 60 + 10 = 145.

Choisir le modèle de tirage

À retenirLes trois modèles de tirage

On tire pp jetons dans une urne de nn jetons tous différents.

Tirage L'ordre compte Répétition possible Objet compté Nombre
successif avec remise oui oui pp-liste npn^p
successif sans remise oui non arrangement AnpA_n^p
simultané non non combinaison CnpC_n^p

MéthodeChoisir le modèle en deux questions

  1. L'ordre compte-t-il ? Oui pour un code, un classement, des postes différents. Non pour un groupe, un lot, une poignée tirée d'un coup.
  2. Un élément peut-il revenir ? Oui avec remise, ou pour un chiffre réutilisable. Non pour des personnes, ou sans remise.
  3. Conclus : ordre et répétition, npn^p ; ordre sans répétition, AnpA_n^p ; ni ordre ni répétition, CnpC_n^p.

Exemple

Une urne fictive contient 88 jetons numérotés. On en tire 33.

  • Successivement avec remise : 83=5128^3 = 512 tirages.
  • Successivement sans remise : A83=8×7×6=336A_8^3 = 8 \times 7 \times 6 = 336 tirages.
  • Simultanément : C83=3363!=3366=56C_8^3 = \dfrac{336}{3!} = \dfrac{336}{6} = 56 tirages.

RemarqueUn lien entre les modèles

Les pp jetons d'un tirage simultané peuvent être rangés de p!p! façons. C'est pourquoi Anp=p!×CnpA_n^p = p! \times C_n^p. Dans l'urne précédente : 336=6×56336 = 6 \times 56.

Propriétés des coefficients

PropriétéPremières propriétés des coefficients

Soit nn un entier naturel non nul.

  • Cn0=Cnn=1C_n^0 = C_n^n = 1 et Cn1=nC_n^1 = n.
  • Pour tout entier pp tel que 0≤p≤n0 \leq p \leq n : Cnn−p=Cnp.C_n^{n - p} = C_n^p.

PropriétéRelation de Pascal

Soit nn un entier tel que n≥2n \geq 2 et pp un entier tel que 1≤p≤n−11 \leq p \leq n - 1. Alors Cnp=Cn−1p−1+Cn−1p.C_n^p = C_{n - 1}^{p - 1} + C_{n - 1}^{p}.

À retenirLe triangle de Pascal

La ligne nn donne Cn0C_n^0, Cn1C_n^1, ..., CnnC_n^n. Les deux bords valent 11. À l'intérieur, la relation de Pascal fait lire la ligne du dessus : on ajoute le nombre de la même colonne et celui de la colonne précédente.

nn p=0p = 0 p=1p = 1 p=2p = 2 p=3p = 3 p=4p = 4 p=5p = 5 p=6p = 6 p=7p = 7
11 11 11
22 11 22 11
33 11 33 33 11
44 11 44 66 44 11
55 11 55 1010 1010 55 11
66 11 66 1515 2020 1515 66 11
77 11 77 2121 3535 3535 2121 77 11

Un triangle de nombres centré, de la ligne 0 au sommet à la ligne 7 à la base. Les deux bords de chaque ligne valent 1. La ligne 6 se lit 1, 6, 15, 20, 15, 6, 1 et la ligne 7 se lit 1, 7, 21, 35, 35, 21, 7, 1 : lues de gauche à droite ou de droite à gauche, elles donnent la même suite. Le 15 et le 20 de la ligne 6 sont teintés, ainsi que le premier 35 de la ligne 7, vers lequel pointent deux flèches.

Les lignes 0 à 7 rangées en triangle : chaque ligne se lit pareil dans les deux sens, et 35 s'obtient en ajoutant 15 et 20 de la ligne 6.

Exemple

Par symétrie, C2018=C202=20×192=190C_{20}^{18} = C_{20}^{2} = \dfrac{20 \times 19}{2} = 190 : on garde le plus petit des deux nombres 1818 et 22. Par la relation de Pascal, C73=C62+C63=15+20=35C_7^3 = C_6^2 + C_6^3 = 15 + 20 = 35, ce que confirme la ligne 77 du triangle.

MéthodeCalculer un coefficient vite et juste

  1. Remplace pp par n−pn - p si n−pn - p est plus petit (symétrie).
  2. Écris au numérateur pp facteurs qui descendent à partir de nn, et p!p! au dénominateur.
  3. Simplifie la fraction avant de multiplier.
  4. Pour les petites valeurs de nn, lis le coefficient dans le triangle de Pascal.

Formule du binôme, nombre de parties, formulaire

ThéorèmeFormule du binôme

Pour tous réels aa et bb et pour tout entier naturel non nul nn : (a+b)n=∑p=0nCnp an−p bp=Cn0 an+Cn1 an−1b+Cn2 an−2b2+⋯+Cnn bn,(a + b)^n = \sum_{p = 0}^{n} C_n^p\, a^{n - p}\, b^{p} = C_n^0\, a^n + C_n^1\, a^{n - 1} b + C_n^2\, a^{n - 2} b^2 + \dots + C_n^n\, b^n, avec la convention x0=1x^0 = 1 pour tout réel xx.

MéthodeDévelopper une puissance d'une somme

  1. Identifie aa, bb et nn, en gardant le signe de bb.
  2. Recopie la ligne nn du triangle de Pascal.
  3. Écris les termes Cnp an−p bpC_n^p\, a^{n - p}\, b^{p} pour pp allant de 00 à nn.
  4. Calcule chaque terme, puis contrôle en remplaçant la variable par 11.

Exemple

Pour (x+3)4(x + 3)^4, on lit la ligne 44 du triangle : 11, 44, 66, 44, 11. (x+3)4=x4+4×3 x3+6×9 x2+4×27 x+81=x4+12x3+54x2+108x+81.(x + 3)^4 = x^4 + 4 \times 3\,x^3 + 6 \times 9\,x^2 + 4 \times 27\,x + 81 = x^4 + 12x^3 + 54x^2 + 108x + 81. Contrôle avec x=1x = 1 : 1+12+54+108+81=256=441 + 12 + 54 + 108 + 81 = 256 = 4^4.

Exemple

Pour (2x−1)3(2x - 1)^3, on prend a=2xa = 2x et b=−1b = -1. (2x−1)3=(2x)3+3×(2x)2×(−1)+3×2x×(−1)2+(−1)3=8x3−12x2+6x−1.(2x - 1)^3 = (2x)^3 + 3 \times (2x)^2 \times (-1) + 3 \times 2x \times (-1)^2 + (-1)^3 = 8x^3 - 12x^2 + 6x - 1. Contrôle avec x=1x = 1 : 8−12+6−1=1=(2−1)38 - 12 + 6 - 1 = 1 = (2 - 1)^3.

AttentionLe signe de b

Écrire (x−2)3=x3−6x2−12x−8(x - 2)^3 = x^3 - 6x^2 - 12x - 8 est faux. Avec b=−2b = -2, on a (−2)1=−2(-2)^1 = -2, (−2)2=4(-2)^2 = 4 et (−2)3=−8(-2)^3 = -8 : les signes ++ et −- alternent devant les termes. Le bon développement est (x−2)3=x3−6x2+12x−8(x - 2)^3 = x^3 - 6x^2 + 12x - 8. Vérifie aussi que, dans chaque terme, les exposants de xx et de −2-2 ont pour somme 33.

Exemple

Coefficient de x5x^5 dans (x+2)7(x + 2)^7 : le terme d'indice pp est C7p x7−p 2pC_7^p\, x^{7 - p}\, 2^{p}. On veut 7−p=57 - p = 5, donc p=2p = 2. Le coefficient vaut C72×22=21×4=84C_7^2 \times 2^2 = 21 \times 4 = 84.

PropriétéNombre de parties d'un ensemble fini

Soit EE un ensemble fini à nn éléments (n≥0n \geq 0). L'ensemble des parties de EE, noté P(E)\mathcal{P}(E), a 2n2^n éléments : card⁡(P(E))=2n.\operatorname{card}(\mathcal{P}(E)) = 2^n. En particulier, pour tout entier naturel non nul nn, Cn0+Cn1+⋯+Cnn=2nC_n^0 + C_n^1 + \dots + C_n^n = 2^n.

Exemple

Un ordinateur se vend avec 44 options facultatives (exemple fictif). Une configuration est une partie de l'ensemble des 44 options : il y en a 24=162^4 = 16. En les classant selon le nombre d'options : C40+C41+C42+C43+C44=1+4+6+4+1=16C_4^0 + C_4^1 + C_4^2 + C_4^3 + C_4^4 = 1 + 4 + 6 + 4 + 1 = 16. Configurations à au moins deux options : 16−1−4=1116 - 1 - 4 = 11.

RemarqueSomme d'une ligne du triangle

Avec a=b=1a = b = 1, la formule du binôme donne Cn0+Cn1+⋯+Cnn=(1+1)n=2nC_n^0 + C_n^1 + \dots + C_n^n = (1 + 1)^n = 2^n. La somme de la ligne nn du triangle de Pascal vaut donc 2n2^n.

Réunion de deux ensembles
card⁡(A∪B)=card⁡(A)+card⁡(B)−card⁡(A∩B)\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B) - \operatorname{card}(A \cap B)
Complémentaire dans E
card⁡(A‾)=card⁡(E)−card⁡(A)\operatorname{card}(\overline{A}) = \operatorname{card}(E) - \operatorname{card}(A)
Produit cartésien
card⁡(E×F)=card⁡(E)×card⁡(F)\operatorname{card}(E \times F) = \operatorname{card}(E) \times \operatorname{card}(F)
p-listes d'un ensemble à n éléments
card⁡(Ep)=np\operatorname{card}(E^p) = n^p
Factorielle
n!=1×2×⋯×n,0!=1n! = 1 \times 2 \times \dots \times n, \quad 0! = 1
Arrangements, p entre 1 et n
Anp=n×(n−1)×⋯×(n−p+1)=n!(n−p)!A_n^p = n \times (n - 1) \times \dots \times (n - p + 1) = \dfrac{n!}{(n - p)!}
Permutations de n éléments
Ann=n!A_n^n = n!
Combinaisons, p entre 0 et n
Cnp=n!p! (n−p)!C_n^p = \dfrac{n!}{p!\,(n - p)!}
Symétrie
Cnn−p=CnpC_n^{n - p} = C_n^p
Relation de Pascal, p entre 1 et n - 1
Cnp=Cn−1p−1+Cn−1pC_n^p = C_{n - 1}^{p - 1} + C_{n - 1}^{p}
Formule du binôme
(a+b)n=∑p=0nCnp an−p bp(a + b)^n = \sum_{p = 0}^{n} C_n^p\, a^{n - p}\, b^{p}
Nombre de parties d'un ensemble à n éléments
card⁡(P(E))=2n\operatorname{card}(\mathcal{P}(E)) = 2^n

À retenirTrois réflexes avant de compter

  • Nomme ce que tu comptes : une liste ordonnée, un groupe sans ordre, une partie ?
  • Cherche les mots « au moins » : ils appellent le contraire, puis une soustraction.
  • Contrôle par un autre chemin : une petite liste écrite à la main, une somme de cas disjoints, ou x=1x = 1 dans un développement.