Aller au contenu

Dénombrement 1 bac SM : cours et résumé

Type
Cours
Lecture
14 min

Dénombrer un ensemble fini EE, c'est calculer son cardinal card(E)\mathrm{card}(E), le nombre de ses éléments, sans les écrire un par un. Pour choisir pp éléments parmi nn, deux questions décident de la formule : l'ordre compte-t-il, et un même élément peut-il revenir ? Avec ordre et répétition, on obtient npn^p listes ; avec ordre et sans répétition (p≤np\leq n), Anp=n!(n−p)!A_n^p=\dfrac{n!}{(n-p)!} arrangements ; sans ordre ni répétition (0≤p≤n0\leq p\leq n), Cnp=n!p! (n−p)!C_n^p=\dfrac{n!}{p!\,(n-p)!} combinaisons. Exemple : parmi 13 candidats, on désigne un délégué et son suppléant de A132=13×12=156A_{13}^2=13\times12=156 façons, mais deux représentants de même rôle de C132=1562=78C_{13}^2=\dfrac{156}{2}=78 façons seulement.

Chapitre du semestre 2 de la 1re année du baccalauréat sciences mathématiques (option française BIOF), après la géométrie analytique de l'espace : il n'existe qu'en 1 bac SM, les sciences expérimentales ne rencontrent le dénombrement qu'en 2e année. Il utilise le vocabulaire des ensembles et applications (réunion, complémentaire, bijection) et le raisonnement par récurrence.

Sommaire11 parties

Résumé de cours : dénombrement en un tableau

EE est un ensemble fini à nn éléments, AA, BB, CC des parties de EE, et pp un entier naturel. Le lien de la première colonne mène à la section correspondante.

NotionÀ retenir
Réunioncard(A∪B)\mathrm{card}(A\cup B)
=card(A)+card(B)=\mathrm{card}(A)+\mathrm{card}(B)
−card(A∩B)\quad-\mathrm{card}(A\cap B)
card(A‾)=n−card(A)\mathrm{card}(\overline{A})=n-\mathrm{card}(A)
Trois ensembleson ajoute les trois cardinaux, on retranche les trois intersections deux à deux, on ajoute le cardinal de l'intersection des trois
Principe fondamental du dénombrementpp choix successifs à n1n_1, …, npn_p possibilités, nombres indépendants des choix précédents :
n1×n2×⋯×npn_1\times n_2\times\cdots\times n_p
card(E×F)\mathrm{card}(E\times F)
=card(E)×card(F)=\mathrm{card}(E)\times\mathrm{card}(F)
Applications, partiesmpm^p applications d'un ensemble à pp éléments dans un ensemble à mm éléments
P(E)\mathcal{P}(E) a 2n2^n éléments
Arrangements avec répétitionordre compté, répétition permise, tout p≥1p\geq1 : npn^p
Arrangements sans répétitionordre compté, sans répétition,
1≤p≤n1\leq p\leq n :
Anp=n(n−1)⋯(n−p+1)A_n^p=n(n-1)\cdots(n-p+1)
Anp=n!(n−p)!A_n^p=\dfrac{n!}{(n-p)!}
Permutationsn!=n×(n−1)×⋯×1n!=n\times(n-1)\times\cdots\times1
0!=10!=1
avec répétition : n!n1! n2!⋯nk!\dfrac{n!}{n_1!\,n_2!\cdots n_k!}
où n1+⋯+nk=nn_1+\cdots+n_k=n
Combinaisonsparties à pp éléments,
0≤p≤n0\leq p\leq n :
Cnp=Anpp!=n!p! (n−p)!C_n^p=\dfrac{A_n^p}{p!}=\dfrac{n!}{p!\,(n-p)!}
Symétrie et relation de PascalCnn−p=CnpC_n^{n-p}=C_n^p, pour 0≤p≤n0\leq p\leq n
Cn+1p=Cnp−1+CnpC_{n+1}^p=C_n^{p-1}+C_n^p,
pour 1≤p≤n1\leq p\leq n
Tiragessimultané (p≤np\leq n) : CnpC_n^p ; successif sans remise (p≤np\leq n) : AnpA_n^p ; successif avec remise (tout p≥1p\geq1) : npn^p
Binôme de Newtonpour n∈N∗n\in\mathbb{N}^* :
(a+b)n=∑k=0nCnk an−k bk(a+b)^n=\displaystyle\sum_{k=0}^{n}C_n^k\,a^{n-k}\,b^k
∑k=0nCnk=2n\displaystyle\sum_{k=0}^{n}C_n^k=2^n
PDF A4 · 2 pages · 114 KoTélécharger le résumé (PDF)

Ensembles finis et cardinal

Ensemble fini et cardinal

Un ensemble EE est fini s'il est vide ou s'il existe un entier n≥1n\geq1 et une bijection de {1 ;2 ;… ;n}\{1\,;2\,;\dots\,;n\} sur EE : on numérote ses éléments de 1 à nn. L'entier nn est le cardinal de EE, noté card(E)\mathrm{card}(E), et card(∅)=0\mathrm{card}(\varnothing)=0. Deux ensembles finis ont le même cardinal lorsqu'il existe une bijection de l'un sur l'autre (admis) : compter EE, c'est souvent le mettre en bijection avec un ensemble plus simple à compter.

Cardinal d’une réunion, d’un complémentaire et d’une différence

Pour toutes parties AA et BB d'un ensemble fini EE :

  • card(A∪B)=card(A)+card(B)−card(A∩B)\mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B)-\mathrm{card}(A\cap B) ;
  • si A∩B=∅A\cap B=\varnothing, card(A∪B)=card(A)+card(B)\mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B) ;
  • card(A‾)=card(E)−card(A)\mathrm{card}(\overline{A})=\mathrm{card}(E)-\mathrm{card}(A) et, si A⊂BA\subset B, card(B∖A)=card(B)−card(A)\mathrm{card}(B\setminus A)=\mathrm{card}(B)-\mathrm{card}(A).

Démonstration : cardinal d’une réunion de deux ensembles

On admet le cas disjoint : en numérotant les éléments de AA puis ceux de BB, on numérote ceux de A∪BA\cup B. Le complémentaire en découle, car EE est la réunion disjointe de AA et A‾\overline{A}. Dans le cas général, A∪BA\cup B est la réunion disjointe de AA et de B∖AB\setminus A, et BB celle de A∩BA\cap B et de B∖AB\setminus A. Donc card(A∪B)=card(A)+card(B∖A)\mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B\setminus A) et card(B)=card(A∩B)+card(B∖A)\mathrm{card}(B)=\mathrm{card}(A\cap B)+\mathrm{card}(B\setminus A). On remplace card(B∖A)\mathrm{card}(B\setminus A) par card(B)−card(A∩B)\mathrm{card}(B)-\mathrm{card}(A\cap B) dans la première égalité. Enfin, si A⊂BA\subset B, alors A∩B=AA\cap B=A et la seconde égalité donne card(B∖A)=card(B)−card(A)\mathrm{card}(B\setminus A)=\mathrm{card}(B)-\mathrm{card}(A).

Exemple 1 : deux clubs dans une classe

Une classe de 1 bac SM compte 34 élèves : 19 sont inscrits au club d'échecs E1E_1, 13 au club de robotique RR, et 6 aux deux. Le nombre d'élèves inscrits à au moins un club est

card(E1∪R)=19+13−6=26.\begin{aligned}&\mathrm{card}(E_1\cup R)\\&=19+13-6=26.\end{aligned}

Il reste 34−26=834-26=8 élèves sans club, et 19−6=1319-6=13 élèves font seulement des échecs.

Attention : on n'ajoute les cardinaux que pour des ensembles disjoints. Ici 19+13=3219+13=32 compte deux fois les 6 élèves inscrits aux deux clubs.

Cardinal de la réunion de trois ensembles

Pour toutes parties AA, BB, CC d'un ensemble fini (formule de Poincaré) :

card(A∪B∪C)=card(A)+card(B)+card(C)−card(A∩B)−card(A∩C)−card(B∩C)+card(A∩B∩C).\begin{aligned}&\mathrm{card}(A\cup B\cup C)\\&=\mathrm{card}(A)+\mathrm{card}(B)\\&\quad+\mathrm{card}(C)\\&\quad-\mathrm{card}(A\cap B)\\&\quad-\mathrm{card}(A\cap C)\\&\quad-\mathrm{card}(B\cap C)\\&\quad+\mathrm{card}(A\cap B\cap C).\end{aligned}

Démonstration : formule de Poincaré pour trois ensembles

On applique la formule de deux ensembles à AA et B∪CB\cup C :

card(A∪B∪C)=card(A)+card(B∪C)−card(A∩(B∪C)).\begin{aligned}&\mathrm{card}(A\cup B\cup C)\\&=\mathrm{card}(A)\\&\quad+\mathrm{card}(B\cup C)\\&\quad-\mathrm{card}(A\cap(B\cup C)).\end{aligned}

D'une part card(B∪C)=card(B)+card(C)−card(B∩C)\mathrm{card}(B\cup C)=\mathrm{card}(B)+\mathrm{card}(C)-\mathrm{card}(B\cap C). D'autre part, par distributivité, A∩(B∪C)=(A∩B)∪(A∩C)A\cap(B\cup C)=(A\cap B)\cup(A\cap C), et l'intersection de ces deux parties est A∩B∩CA\cap B\cap C, donc card(A∩(B∪C))=card(A∩B)+card(A∩C)−card(A∩B∩C)\mathrm{card}(A\cap(B\cup C))=\mathrm{card}(A\cap B)+\mathrm{card}(A\cap C)-\mathrm{card}(A\cap B\cap C). On remplace ces deux cardinaux dans l'égalité précédente.

Exemple 2 : entiers divisibles par 3, 4 ou 5

Dans E={1 ;2 ;… ;300}E=\{1\,;2\,;\dots\,;300\}, soient TT, QQ, FF les multiples de 3, de 4 et de 5. Comme 3, 4, 5, 12, 15, 20 et 60 divisent 300, l'ensemble des multiples de dd a 300d\frac{300}{d} éléments. Les entiers multiples à la fois de 3 et de 4 sont les multiples de leur PPCM 12 ; de même, T∩FT\cap F, Q∩FQ\cap F et T∩Q∩FT\cap Q\cap F sont formés des multiples de 15, 20 et 60. Donc

card(T∪Q∪F)=100+75+60−25−20−15+5=180.\begin{aligned}&\mathrm{card}(T\cup Q\cup F)\\&=100+75+60\\&\quad-25-20-15+5\\&=180.\end{aligned}

Ainsi 300−180=120300-180=120 entiers de EE ne sont divisibles ni par 3, ni par 4, ni par 5.

Principe fondamental du dénombrement et produit cartésien

Principe fondamental du dénombrement

Une situation se décompose en pp choix successifs. Le premier choix se fait de n1n_1 façons ; puis, quel que soit ce premier choix, le deuxième se fait de n2n_2 façons, et ainsi de suite jusqu'au dernier, de npn_p façons. Le nombre total de résultats est alors n1×n2×⋯×npn_1\times n_2\times\cdots\times n_p. On l'appelle aussi principe multiplicatif et on le visualise par un arbre de choix.

En particulier, pour des ensembles finis EE et FF, le produit cartésien vérifie card(E×F)=card(E)×card(F)\mathrm{card}(E\times F)=\mathrm{card}(E)\times\mathrm{card}(F), et plus généralement card(E1×⋯×Ep)=card(E1)×⋯×card(Ep)\mathrm{card}(E_1\times\cdots\times E_p)=\mathrm{card}(E_1)\times\cdots\times\mathrm{card}(E_p).

Les possibilités d'une étape peuvent changer selon la branche de l'arbre ; seul leur nombre doit rester le même.

Exemple 3 : étiquettes des casiers d’un lycée

Une étiquette de casier est formée d'une lettre de A à F, suivie de deux chiffres distincts pris de 1 à 9 (par exemple C47). On choisit la lettre (6 façons), le premier chiffre (9 façons), puis le second parmi les 8 chiffres restants. Les chiffres restants dépendent du premier choix, mais leur nombre vaut toujours 8 :

6×9×8=432 eˊtiquettes.6\times9\times8=432\ \text{étiquettes}.

Nombre d’applications et nombre de parties

Applications d’un ensemble fini dans un autre

  • Si card(E)=p\mathrm{card}(E)=p et card(F)=m\mathrm{card}(F)=m, avec p≥1p\geq1 et m≥1m\geq1, le nombre d'applications de EE dans FF est mpm^p.
  • Si card(E)=n\mathrm{card}(E)=n, l'ensemble P(E)\mathcal{P}(E) des parties de EE a 2n2^n éléments.

Démonstration : nombre d’applications et nombre de parties

Numérotons E={x1 ;… ;xp}E=\{x_1\,;\dots\,;x_p\}. Une application ff est déterminée par le choix de f(x1)f(x_1) dans FF (mm façons), puis de f(x2)f(x_2) (mm façons), jusqu'à f(xp)f(x_p) : le principe multiplicatif donne mpm^p. Pour les parties, on associe à chaque partie AA de EE l'application φA:E→{0 ;1}\varphi_A:E\to\{0\,;1\} qui vaut 1 sur AA et 0 hors de AA. Cette correspondance est une bijection : une application φ\varphi de EE dans {0 ;1}\{0\,;1\} provient de la seule partie {x∈E / φ(x)=1}\{x\in E\ /\ \varphi(x)=1\}. Donc card(P(E))=2n\mathrm{card}(\mathcal{P}(E))=2^n. Pour n=0n=0, P(∅)={∅}\mathcal{P}(\varnothing)=\{\varnothing\} a bien 1=201=2^0 élément.

Exemple 4 : quatre élèves et six clubs

Le lycée propose 6 clubs. Quatre élèves choisissent chacun un club : un choix global est une application de l'ensemble des 4 élèves dans celui des 6 clubs, d'où 64=12966^4=1296 possibilités. Si les quatre clubs choisis doivent être distincts, on compte les applications injectives : 6×5×4×3=3606\times5\times4\times3=360. Un élève qui peut s'inscrire à autant de clubs qu'il veut choisit une partie de l'ensemble des clubs : 26=642^6=64 choix, la partie vide (aucun club) et l'ensemble des six clubs compris.

Arrangements avec répétition et sans répétition

Arrangements avec répétition (p-listes)

Soit EE un ensemble à nn éléments et p≥1p\geq1. Un arrangement avec répétition de pp éléments de EE est une liste ordonnée (x1 ;… ;xp)(x_1\,;\dots\,;x_p) d'éléments de EE, non nécessairement distincts. C'est un élément de EpE^p : il y en a npn^p, et pp peut dépasser nn.

Factorielle d’un entier naturel

Pour n≥1n\geq1, n!=n×(n−1)×⋯×2×1n!=n\times(n-1)\times\cdots\times2\times1 (« factorielle nn »), et l'on pose 0!=10!=1. Pour n≥1n\geq1, n!=n×(n−1)!n!=n\times(n-1)! ; par exemple 6!=7206!=720.

Arrangements sans répétition

Soit 1≤p≤n1\leq p\leq n. Un arrangement de pp éléments de EE est une liste ordonnée de pp éléments distincts de EE, autrement dit une application injective de {1 ;… ;p}\{1\,;\dots\,;p\} dans EE. Leur nombre est

Anp=n(n−1)⋯(n−p+1)=n!(n−p)!.\begin{aligned}A_n^p&=n(n-1)\cdots(n-p+1)\\&=\frac{n!}{(n-p)!}.\end{aligned}

Le produit a pp facteurs décroissants à partir de nn. On pose An0=1A_n^0=1.

Démonstration : nombre d’arrangements sans répétition

Le premier élément de la liste se choisit de nn façons ; quel que soit ce choix, le deuxième se choisit parmi les n−1n-1 autres, et ainsi de suite : le pp-ième se choisit parmi les n−(p−1)n-(p-1) éléments non encore utilisés. Le principe multiplicatif donne Anp=n(n−1)⋯(n−p+1)A_n^p=n(n-1)\cdots(n-p+1). En multipliant et en divisant par (n−p)!=(n−p)×⋯×1(n-p)!=(n-p)\times\cdots\times1, on complète le produit jusqu'à 1, d'où Anp=n!(n−p)!A_n^p=\dfrac{n!}{(n-p)!}.

Exemple 5 : cadenas de vélo à quatre molettes

Chacune des 4 molettes d'un cadenas porte les chiffres 1 à 7. Un code est une liste ordonnée de 4 chiffres où un chiffre peut revenir : 74=24017^4=2401 codes. Si l'on impose 4 chiffres distincts, ce sont des arrangements sans répétition : A74=7×6×5×4=840A_7^4=7\times6\times5\times4=840 codes.

Permutations simples et permutations avec répétition

Permutations d’un ensemble fini

Une permutation d'un ensemble EE à nn éléments (n≥1n\geq1) est un arrangement de tous ses éléments : une façon de les ranger en ligne, ou encore une bijection de EE sur EE. Il y en a Ann=n!A_n^n=n!.

Exemple 6 : aligner les onze joueurs d’une équipe

Les 11 joueurs d'une équipe de football s'alignent pour la photo : 11!=39 916 80011!=39\,916\,800 alignements. Si le capitaine et le gardien doivent être côte à côte, ils forment un bloc : on range 10 objets, puis les deux joueurs dans le bloc, soit 2×10!=7 257 6002\times10!=7\,257\,600 alignements.

Permutations avec répétition et anagrammes

On range en ligne nn objets de kk types : n1n_1 objets identiques du premier type, …, nkn_k du dernier, avec n1+n2+⋯+nk=nn_1+n_2+\cdots+n_k=n. Le nombre de rangements distincts est

n!n1! n2!⋯nk!.\frac{n!}{n_1!\,n_2!\cdots n_k!}.

En effet, si l'on numérote les objets pour les distinguer, on obtient n!n! rangements. Chaque rangement sans numéros est alors obtenu n1!×⋯×nk!n_1!\times\cdots\times n_k! fois, en permutant entre eux les objets d'un même type.

Exemple 7 : anagrammes de OUARZAZATE

Le mot OUARZAZATE a 10 lettres : trois A, deux Z, et O, U, R, T, E une fois chacune. Le nombre de mots de 10 lettres, ayant un sens ou non, formés avec exactement ces lettres est

10!3!×2!=3 628 80012=302 400.\frac{10!}{3!\times2!}=\frac{3\,628\,800}{12}=302\,400.

Combinaisons : choisir une partie sans ordre

Combinaisons d’un ensemble à n éléments

Soit 0≤p≤n0\leq p\leq n. Une combinaison de pp éléments de EE est une partie de EE à pp éléments : l'ordre n'intervient pas et il n'y a pas de répétition. Leur nombre est

Cnp=Anpp!=n!p! (n−p)!.C_n^p=\frac{A_n^p}{p!}=\frac{n!}{p!\,(n-p)!}.

On a Cn0=Cnn=1C_n^0=C_n^n=1 (la partie vide et EE) et Cn1=nC_n^1=n (les singletons). On rencontre aussi la notation (np)\binom{n}{p}.

Démonstration : nombre de combinaisons

Soit 1≤p≤n1\leq p\leq n. On fabrique un arrangement de pp éléments en deux étapes : on choisit la partie de ses éléments (CnpC_n^p façons), puis on range cette partie en ligne (p!p! façons). Chaque arrangement est obtenu une seule fois, car sa partie est l'ensemble de ses termes. Le principe multiplicatif donne Anp=Cnp×p!A_n^p=C_n^p\times p!. Pour p=0p=0, la formule donne n!0! n!=1\frac{n!}{0!\,n!}=1, le nombre de parties vides.

Exemple 8 : commission ou bureau dans une classe de 17 élèves

Une commission de 3 élèves aux rôles identiques est une partie de la classe :

C173=17×16×153×2×1=680.C_{17}^3=\frac{17\times16\times15}{3\times2\times1}=680.

Un bureau formé d'un président, d'un secrétaire et d'un trésorier, trois élèves distincts, est une liste ordonnée : A173=17×16×15=4080=3!×680A_{17}^3=17\times16\times15=4080=3!\times680.

Attention : l'ordre ne compte que si les rôles sont différents ou si l'énoncé parle de rang. « Choisir 3 élèves » se compte avec CnpC_n^p ; « classer 3 élèves » avec AnpA_n^p.

Symétrie, relation de Pascal et triangle de Pascal

Symétrie et relation de Pascal

  • Pour 0≤p≤n0\leq p\leq n : Cnn−p=CnpC_n^{n-p}=C_n^p.
  • Pour 1≤p≤n1\leq p\leq n : Cn+1p=Cnp−1+CnpC_{n+1}^p=C_n^{p-1}+C_n^p (relation de Pascal).

Démonstration : symétrie et relation de Pascal

Symétrie : si XX a pp éléments, X‾\overline{X} en a n−pn-p. L'application X↦X‾X\mapsto\overline{X}, des parties à pp éléments dans les parties à n−pn-p éléments, est une bijection : sa réciproque est Y↦Y‾Y\mapsto\overline{Y}, car le complémentaire du complémentaire d'une partie est cette partie. Les deux ensembles de parties ont donc le même cardinal. Pascal, pour 1≤p≤n{1\leq p\leq n}, avec (n−p+1)!=(n−p+1)×(n−p)!{(n-p+1)!}={(n-p+1)}\times{(n-p)!} et p!=p×(p−1)!p!=p\times{(p-1)!}, puis on réduit au même dénominateur p! (n−p+1)!p!\,(n-p+1)! :

Cnp−1+Cnp=n! pp! (n−p+1)!+n! (n−p+1)p! (n−p+1)!=n! (p+n−p+1)p! (n−p+1)!=(n+1)!p! (n+1−p)!=Cn+1p.\begin{aligned}&C_n^{p-1}+C_n^p\\&=\frac{n!\,p}{p!\,(n-p+1)!}\\&\quad+\frac{n!\,(n-p+1)}{p!\,(n-p+1)!}\\&=\frac{n!\,(p+n-p+1)}{p!\,(n-p+1)!}\\&=\frac{(n+1)!}{p!\,(n+1-p)!}=C_{n+1}^p.\end{aligned}

Triangle de Pascal

La ligne nn donne Cn0C_n^0, Cn1C_n^1, …, CnnC_n^n, la colonne pp (en-tête de la table) contenant CnpC_n^p ; chaque nombre qui n'est pas au bout de sa ligne est la somme du nombre situé juste au-dessus et du voisin de gauche de ce dernier : c'est la relation Cn+1p=Cnp−1+CnpC_{n+1}^p=C_n^{p-1}+C_n^p.

n\pn\backslash p0123456
01
111
2121
31331
414641
515101051
61615201561

Exemple 9 : lire et contrôler une valeur du triangle

Par symétrie, C64=C62=6×52=15C_6^4=C_6^2=\dfrac{6\times5}{2}=15, et la relation de Pascal le confirme : C64=C53+C54=10+5C_6^4=C_5^3+C_5^4=10+5. La somme de la ligne 6 vaut 1+6+15+20+15+6+1=64=261+6+15+20+15+6+1=64=2^6 : on a compté les parties d'un ensemble à 6 éléments selon leur nombre d'éléments.

Tirages avec ou sans remise et tirages simultanés

On tire pp objets parmi nn objets discernables (boules numérotées, jetons, cartes). Le mode de tirage fixe l'objet que l'on compte.

Choisir le bon outil de dénombrement

Trois questions, posées dans cet ordre, donnent la formule :

  1. L'ordre compte-t-il ? Non : on choisit une partie, CnpC_n^p.
  2. Oui, et l'on range tous les nn objets : permutation, n!n!, ou n!n1!⋯nk!\dfrac{n!}{n_1!\cdots n_k!} si certains objets sont identiques.
  3. Oui, et l'on n'en prend que pp : avec répétition npn^p ; sans répétition AnpA_n^p, avec p≤n{p\leq n}.
Situation : ordre ? répétition ?Nombre
tirages successifs avec remise : ordre oui, répétition ouinpn^p
tirages successifs sans remise, p≤n{p\leq n} : ordre oui, répétition nonAnpA_n^p
rangement de tous les nn objets : ordre oui, répétition nonn!n!
tirages simultanés, p≤n{p\leq n} : ordre non, répétition nonCnpC_n^p
rangement de tous les objets, n1n_1, …, nkn_k identiques entre euxn!n1!⋯nk!\dfrac{n!}{n_1!\cdots n_k!}

Exemple 10 : huit jetons numérotés, trois modes de tirage

Un sac contient 8 jetons numérotés de 1 à 8 (quatre pairs, quatre impairs). On tire 3 jetons et l'on compte les tirages qui donnent exactement deux numéros pairs.

  • Simultané : un tirage est une partie à 3 éléments, C83=56C_8^3=56 tirages. On choisit 2 pairs et 1 impair : C42×C41=6×4=24C_4^2\times C_4^1=6\times4=24.
  • Successif sans remise : un tirage est un arrangement, A83=336A_8^3=336. On choisit le rang de l'impair (3 façons), les deux pairs dans l'ordre (A42=12A_4^2=12), puis l'impair (4) : 3×12×4=1443\times12\times4=144.
  • Successif avec remise : une liste avec répétition, 83=5128^3=512. Même découpage : 3×42×4=1923\times4^2\times4=192.

Contrôle : chaque tirage simultané se range de 3!=63!=6 façons, d'où 6×56=3366\times56=336 et 6×24=1446\times24=144.

Attention : « au moins un » se compte par le contraire. Les tirages simultanés avec au moins un pair sont 56−C43=5256-C_4^3=52. Imposer d'abord un pair (4 façons), puis prendre deux jetons quelconques (C72=21C_7^2=21) donne 84 : les tirages à deux ou trois pairs sont comptés plusieurs fois.

Formule du binôme de Newton

Énoncé de la formule du binôme

Pour tous réels aa et bb et tout entier n≥1n\geq1 :

(a+b)n=∑k=0nCnk an−k bk.(a+b)^n=\sum_{k=0}^{n}C_n^k\,a^{n-k}\,b^k.

Les coefficients forment la ligne nn du triangle de Pascal. Avec a=b=1a=b=1, on obtient ∑k=0nCnk=2n\sum_{k=0}^{n}C_n^k=2^n ; avec a=1a=1 et b=−1b=-1, ∑k=0n(−1)kCnk=0\sum_{k=0}^{n}(-1)^kC_n^k=0.

Démonstration : formule du binôme par récurrence

On raisonne par récurrence sur n≥1n\geq1.

  • Initialisation : pour n=1n=1, C10 a+C11 b=a+bC_1^0\,a+C_1^1\,b=a+b.
  • Hérédité : soit n≥1n\geq1 un entier fixé tel que (a+b)n=∑k=0nCnk an−k bk{(a+b)^n}=\sum_{k=0}^{n}C_n^k\,a^{n-k}\,b^k (hypothèse de récurrence). On écrit (a+b)n+1=a(a+b)n+b(a+b)n{(a+b)^{n+1}}={a(a+b)^n}+{b(a+b)^n} et l'on remplace (a+b)n(a+b)^n grâce à l'hypothèse de récurrence : (a+b)n+1=∑k=0nCnk an+1−kbk+∑k=0nCnk an−kbk+1.\begin{aligned}&(a+b)^{n+1}\\&=\sum_{k=0}^{n}C_n^k\,a^{n+1-k}b^k\\&\quad+\sum_{k=0}^{n}C_n^k\,a^{n-k}b^{k+1}.\end{aligned} Dans la seconde somme, on pose j=k+1j=k+1 (jj va de 1 à n+1n+1), puis on renomme jj en kk : elle devient ∑k=1n+1Cnk−1 an+1−kbk\sum_{k=1}^{n+1}C_n^{k-1}\,a^{n+1-k}b^k. Le terme k=0k=0 n'apparaît que dans la première somme et vaut an+1a^{n+1} ; le terme k=n+1k=n+1 n'apparaît que dans la seconde et vaut bn+1b^{n+1} ; pour 1≤k≤n1\leq k\leq n, le coefficient de an+1−kbka^{n+1-k}b^k est Cnk+Cnk−1=Cn+1kC_n^k+C_n^{k-1}=C_{n+1}^k par la relation de Pascal. Comme Cn+10=Cn+1n+1=1C_{n+1}^0=C_{n+1}^{n+1}=1, on obtient la formule au rang n+1n+1.
  • Conclusion : la formule est vraie pour tout entier n≥1n\geq1.

Exemple 11 : développer une puissance cinquième

On prend a=xa=x, b=−2b=-2 et la ligne 5 du triangle : 1, 5, 10, 10, 5, 1.

(x−2)5=x5+5x4(−2)+10x3(−2)2+10x2(−2)3+5x(−2)4+(−2)5=x5−10x4+40x3−80x2+80x−32.\begin{aligned}(x-2)^5&=x^5+5x^4(-2)\\&\quad+10x^3(-2)^2\\&\quad+10x^2(-2)^3\\&\quad+5x(-2)^4+(-2)^5\\&=x^5-10x^4+40x^3\\&\quad-80x^2+80x-32.\end{aligned}

Contrôle avec x=1x=1 : 1−10+40−80+80−32=−1=(1−2)51-10+40-80+80-32=-1=(1-2)^5.

Attention : quand bb est négatif, la puissance bkb^k porte le signe, et les signes alternent ; on écrit (−2)k(-2)^k avec ses parenthèses.

Pages liées