Mathématiques · Dénombrement

Dénombrement

Cardinal, principe multiplicatif, p-listes, arrangements, permutations, combinaisons, binôme de Newton et tirages.

Niveau
1ère Bac
Session
Semestre 2
Cours الدرس

I. Ensembles finis

1. Cardinal d’un ensemble fini

Activité

Dans une classe de \(34\) élèves, \(20\) pratiquent le football, \(13\) pratiquent le basket-ball et \(6\) pratiquent les deux sports.

1) Combien d’élèves pratiquent seulement le football ? seulement le basket-ball ?

2) Combien d’élèves pratiquent au moins un des deux sports ? aucun des deux ?

Solution :

1) Seulement le football : \(20-6=14\) ; seulement le basket-ball : \(13-6=7\).

2) Au moins un sport : \(14+7+6=27\), c’est-à-dire \(20+13-6\) (les \(6\) élèves comptés deux fois sont retirés une fois). Aucun sport : \(34-27=7\).

Définitions

✓ Un ensemble \(E\) est fini s’il est vide ou s’il existe un entier \(n\ge1\) et une bijection de \(\{1;2;\ldots;n\}\) vers \(E\). L’entier \(n\) est le nombre d’éléments de \(E\) : on l’appelle le cardinal de \(E\) et on le note \(\mathrm{card}(E)\). Par convention \(\mathrm{card}(\varnothing)=0\).

✓ Dénombrer un ensemble fini, c’est déterminer son cardinal.

Propriétés

Soient \(A\) et \(B\) deux parties d’un ensemble fini \(E\) :

✓ si \(A\cap B=\varnothing\) (parties disjointes) : \(\mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B)\) ;

✓ dans tous les cas : \(\mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B)-\mathrm{card}(A\cap B)\) ;

✓ le complémentaire \(\overline{A}\) de \(A\) dans \(E\) vérifie \(\mathrm{card}(\overline{A})=\mathrm{card}(E)-\mathrm{card}(A)\) ;

✓ si \(A_{1}\), \(A_{2}\), …, \(A_{p}\) forment une partition de \(E\) (parties non vides, deux à deux disjointes, de réunion \(E\)) : \(\mathrm{card}(E)=\mathrm{card}(A_{1})+\mathrm{card}(A_{2})+\ldots+\mathrm{card}(A_{p})\).

Application 1

Un groupe de \(40\) touristes : \(25\) parlent le français, \(18\) parlent l’anglais et \(7\) parlent les deux langues.

1) Combien de touristes parlent au moins une des deux langues ?

2) Combien ne parlent aucune des deux langues ?

3) Combien parlent une seule des deux langues ?

Solution :

On note \(F\) et \(A\) les ensembles des touristes parlant le français et l’anglais.

1)

\(\mathrm{card}(F\cup A)=25+18-7=36\).

2)

\(\mathrm{card}(\overline{F\cup A})=40-36=4\).

3)

\(\mathrm{card}(F\cup A)-\mathrm{card}(F\cap A)=36-7=29\) (soit \(18\) seulement en français et \(11\) seulement en anglais).

Application 2

Soit \(E=\{1;2;3;\ldots;100\}\).

1) Combien d’éléments de \(E\) sont divisibles par \(2\) ? par \(3\) ? par \(6\) ?

2) Combien d’éléments de \(E\) sont divisibles par \(2\) ou par \(3\) ?

3) En déduire le nombre d’éléments de \(E\) qui ne sont divisibles ni par \(2\) ni par \(3\).

Solution :

1)

Les multiples de \(2\) sont \(2\times1\), …, \(2\times50\) : il y en a \(50\). Les multiples de \(3\) sont \(3\times1\), …, \(3\times33\) (\(3\times33=99\)) : \(33\). Les multiples de \(6\) : \(6\times16=96\), il y en a \(16\).

2)

Un entier est divisible par \(2\) et par \(3\) si et seulement s’il est divisible par \(6\) : \(50+33-16=67\).

3)

On passe au complémentaire : \(100-67=33\).

2. Produit cartésien et principe multiplicatif

Propriété

Si \(E\) et \(F\) sont deux ensembles finis : \(\mathrm{card}(E\times F)=\mathrm{card}(E)\times\mathrm{card}(F)\). Plus généralement :

\(\displaystyle \mathrm{card}\left(E_{1}\times E_{2}\times\ldots\times E_{p}\right)=\mathrm{card}\left(E_{1}\right)\times\mathrm{card}\left(E_{2}\right)\times\ldots\times\mathrm{card}\left(E_{p}\right)\)

Principe fondamental du dénombrement

Si une situation comporte \(p\) choix successifs, le premier pouvant se faire de \(n_{1}\) façons, le deuxième de \(n_{2}\) façons (quel que soit le premier choix), …, le \(p\)-ième de \(n_{p}\) façons, alors le nombre total de possibilités est :

\[n_{1}\times n_{2}\times\ldots\times n_{p}\]

On peut représenter la situation par un arbre de choix : chaque chemin de la racine à une extrémité correspond à une possibilité.

Application 3

1) Un restaurant propose \(3\) entrées, \(4\) plats et \(2\) desserts. Combien de menus « entrée – plat – dessert » peut-on composer ?

2) Une plaque d’immatriculation est formée de \(2\) lettres (parmi \(26\)) suivies de \(4\) chiffres. Combien de plaques peut-on former ?

3) On lance une pièce de monnaie puis un dé à six faces. Représenter les résultats possibles par un arbre et les compter.

Solution :

1)

\(3\times4\times2=24\) menus.

2)

\(26\times26\times10\times10\times10\times10=26^{2}\times10^{4}=6760000\) plaques.

3)

Chaque face de la pièce (\(P\) ou \(F\)) est suivie de six branches \(1\), …, \(6\) : \(2\times6=12\) résultats, de \((P;1)\) à \((F;6)\).

Application 4

1) Vérifier que \(360=2^{3}\times3^{2}\times5\). Un diviseur positif de \(360\) s’écrit \(2^{a}\times3^{b}\times5^{c}\) avec \(0\le a\le3\), \(0\le b\le2\), \(0\le c\le1\). Combien \(360\) a-t-il de diviseurs positifs ?

2) Combien de ces diviseurs sont pairs ? Combien sont multiples de \(15\) ?

Solution :

1)

\(360=8\times45=2^{3}\times3^{2}\times5\). On choisit \(a\) (\(4\) façons), puis \(b\) (\(3\) façons), puis \(c\) (\(2\) façons) : \(4\times3\times2=24\) diviseurs.

2)

Pairs : \(a\in\{1;2;3\}\), d’où \(3\times3\times2=18\). Multiples de \(15\) : \(b\ge1\) et \(c=1\), d’où \(4\times2\times1=8\).

II. Les p-listes (arrangements avec répétition)

Définition et propriété

Soient \(E\) un ensemble à \(n\) éléments et \(p\in\mathbb{N}^{*}\). Une \(p\)-liste (ou \(p\)-uplet) d’éléments de \(E\) est une suite ordonnée \((x_{1};x_{2};\ldots;x_{p})\) d’éléments de \(E\), non nécessairement distincts ; c’est un élément de \(E^{p}\).

Le nombre de \(p\)-listes d’un ensemble à \(n\) éléments est \(n^{p}\).

Démonstration

Pour former une \(p\)-liste, on choisit \(x_{1}\) (\(n\) façons), puis \(x_{2}\) (\(n\) façons), …, puis \(x_{p}\) (\(n\) façons) : principe multiplicatif, \(n\times n\times\ldots\times n=n^{p}\).

Conséquences

✓ Le nombre d’applications d’un ensemble à \(p\) éléments vers un ensemble à \(n\) éléments est \(n^{p}\) (une application de \(\{a_{1};\ldots;a_{p}\}\) vers \(F\) est déterminée par la \(p\)-liste \((f(a_{1});\ldots;f(a_{p}))\)).

✓ Le nombre de parties d’un ensemble \(E\) à \(n\) éléments est \(2^{n}\) : à chaque partie \(A\), on associe l’application de \(E\) vers \(\{0;1\}\) qui vaut \(1\) sur \(A\) et \(0\) ailleurs. On note \(\mathcal{P}(E)\) l’ensemble des parties de \(E\) : \(\mathrm{card}(\mathcal{P}(E))=2^{n}\).

Application 5

1) Combien de codes secrets de \(4\) chiffres (de \(0\) à \(9\)) peut-on former ?

2) On lance un dé à six faces trois fois de suite et on note la suite des résultats. Combien y a-t-il de résultats possibles ? Combien ne contiennent pas le \(6\) ? Combien contiennent au moins un \(6\) ?

3) Combien y a-t-il de nombres de trois chiffres (le premier chiffre est non nul) ?

4) Écrire toutes les parties de \(E=\{a;b;c\}\) et vérifier leur nombre.

Solution :

1)

Ce sont les \(4\)-listes de \(\{0;1;\ldots;9\}\) : \(10^{4}=10000\) codes.

2)

\(6^{3}=216\) résultats. Sans \(6\) : \(3\)-listes de \(\{1;\ldots;5\}\), soit \(5^{3}=125\). Au moins un \(6\) (complémentaire) : \(216-125=91\).

3)

\(9\times10\times10=900\) (de \(100\) à \(999\)).

4)

\(\varnothing\), \(\{a\}\), \(\{b\}\), \(\{c\}\), \(\{a;b\}\), \(\{a;c\}\), \(\{b;c\}\), \(\{a;b;c\}\) : \(8=2^{3}\) parties.

Application 6

1) De combien de façons peut-on distribuer \(5\) lettres différentes dans \(3\) boîtes aux lettres ?

2) Combien y a-t-il d’applications de \(E=\{1;2;3;4\}\) vers \(F=\{a;b\}\) ? Combien sont surjectives ?

3) Un questionnaire comporte \(8\) questions auxquelles on répond par « vrai » ou « faux ». Combien de grilles de réponses différentes existe-t-il ?

Solution :

1)

Chaque lettre a \(3\) destinations possibles : \(3^{5}=243\) façons.

2)

\(2^{4}=16\) applications. Seules les deux applications constantes ne sont pas surjectives : \(16-2=14\) surjections.

3)

\(2^{8}=256\) grilles.

III. Arrangements et permutations

Factorielle

Pour tout \(n\in\mathbb{N}^{*}\), on appelle factorielle \(n\) le nombre \(n!=1\times2\times3\times\ldots\times n\). Par convention \(0!=1\). On a \((n+1)!=(n+1)\times n!\).

Arrangements

Soient \(E\) un ensemble à \(n\) éléments et \(p\) un entier avec \(1\le p\le n\). Un arrangement de \(p\) éléments de \(E\) est une \(p\)-liste d’éléments deux à deux distincts de \(E\). Leur nombre est :

\(\displaystyle A_{n}^{p}=n(n-1)(n-2)\cdots(n-p+1)=\frac{n!}{(n-p)!}\)

(produit de \(p\) facteurs consécutifs décroissants à partir de \(n\)). Par convention \(A_{n}^{0}=1\).

Démonstration

On choisit le premier élément (\(n\) façons), puis le deuxième parmi les \(n-1\) restants, …, le \(p\)-ième parmi les \(n-p+1\) restants.

Permutations

Une permutation de \(E\) (\(\mathrm{card}(E)=n\)) est un arrangement des \(n\) éléments de \(E\). Leur nombre est \(A_{n}^{n}=n!\).

✓ Le nombre d’applications injectives d’un ensemble à \(p\) éléments vers un ensemble à \(n\) éléments (\(p\le n\)) est \(A_{n}^{p}\).

✓ Le nombre de bijections d’un ensemble à \(n\) éléments sur lui-même est \(n!\).

Application 7

1) Calculer \(5!\), \(\frac{8!}{6!}\), \(A_{7}^{3}\) et \(A_{10}^{2}\).

2) Simplifier \(\frac{(n+1)!}{(n-1)!}\) et \(\frac{1}{n!}-\frac{1}{(n+1)!}\) pour \(n\ge1\).

3) Résoudre dans \(\mathbb{N}\) l’équation \(A_{n}^{2}=56\), puis l’équation \(A_{n}^{3}=6A_{n}^{2}\).

Solution :

1)

\(5!=120\) ; \(\frac{8!}{6!}=8\times7=56\) ; \(A_{7}^{3}=7\times6\times5=210\) ; \(A_{10}^{2}=10\times9=90\).

2)

\(\frac{(n+1)!}{(n-1)!}=(n+1)n\) ; \(\frac{1}{n!}-\frac{1}{(n+1)!}=\frac{(n+1)-1}{(n+1)!}=\frac{n}{(n+1)!}\).

3)

Pour \(n\ge2\) : \(n(n-1)=56\iff n^{2}-n-56=0\iff(n-8)(n+7)=0\), donc \(n=8\). Pour \(n\ge3\) : \(n(n-1)(n-2)=6n(n-1)\iff n-2=6\iff n=8\).

Application 8

1) Une association de \(30\) membres élit un président, un vice-président et un secrétaire (trois personnes différentes). Combien de bureaux possibles ?

2) De combien de façons peut-on ranger \(6\) livres différents sur une étagère ? et si deux livres donnés doivent être côte à côte ?

3) Combien de mots de \(3\) lettres distinctes peut-on former avec les lettres du mot « MAROC » ?

Solution :

1)

L’ordre compte (les postes sont différents) et il n’y a pas de répétition : \(A_{30}^{3}=30\times29\times28=24360\).

2)

\(6!=720\) rangements. Si les deux livres sont collés, on les considère comme un bloc : \(5!\) façons de ranger les \(5\) « objets », puis \(2\) ordres dans le bloc, soit \(2\times5!=240\).

3)

Les \(5\) lettres sont distinctes : \(A_{5}^{3}=60\) mots.

Application 9

1) Combien de nombres de \(4\) chiffres distincts peut-on écrire (le premier chiffre est non nul) ?

2) Parmi eux, combien sont pairs ?

Solution :

1)

Premier chiffre : \(9\) choix (de \(1\) à \(9\)) ; deuxième : \(9\) choix (le \(0\) redevient possible) ; troisième : \(8\) ; quatrième : \(7\). Total : \(9\times9\times8\times7=4536\).

2)

On commence par le dernier chiffre. S’il est \(0\) : \(9\times8\times7=504\) nombres. S’il est \(2\), \(4\), \(6\) ou \(8\) (\(4\) choix) : premier chiffre \(8\) choix (ni \(0\) ni le dernier), puis \(8\), puis \(7\) : \(4\times8\times8\times7=1792\). Total : \(504+1792=2296\).

Remarque

Lorsqu’un choix impose une contrainte (chiffre non nul, parité…), on commence par l’emplacement le plus contraint, et on distingue des cas si nécessaire.

IV. Combinaisons

Activité

Soit \(E=\{a;b;c;d\}\).

1) Écrire toutes les parties de \(E\) à deux éléments.

2) Écrire tous les arrangements de deux éléments de \(E\). Comparer leur nombre au précédent.

Solution :

1) \(\{a;b\}\), \(\{a;c\}\), \(\{a;d\}\), \(\{b;c\}\), \(\{b;d\}\), \(\{c;d\}\) : \(6\) parties.

2) \(A_{4}^{2}=12\) arrangements : chaque partie \(\{x;y\}\) donne deux arrangements \((x;y)\) et \((y;x)\), donc \(12=2!\times6\).

Définition et propriété

Soient \(E\) un ensemble à \(n\) éléments et \(p\) un entier avec \(0\le p\le n\). Une combinaison de \(p\) éléments de \(E\) est une partie de \(E\) à \(p\) éléments. Leur nombre est :

\[C_{n}^{p}=\frac{A_{n}^{p}}{p!}=\frac{n!}{p!\,(n-p)!}\]

Démonstration

Chaque combinaison de \(p\) éléments donne \(p!\) arrangements (on ordonne ses éléments de toutes les façons), et tout arrangement s’obtient ainsi une seule fois : \(A_{n}^{p}=p!\times C_{n}^{p}\).

Propriétés

Pour tous entiers \(n\) et \(p\) avec \(0\le p\le n\) :

✓ \(C_{n}^{0}=C_{n}^{n}=1\) ; \(C_{n}^{1}=n\) ; \(C_{n}^{2}=\frac{n(n-1)}{2}\) ;

✓ \(C_{n}^{p}=C_{n}^{n-p}\) (choisir les \(p\) éléments retenus revient à choisir les \(n-p\) éléments écartés) ;

✓ relation de Pascal : pour \(1\le p\le n-1\), \(C_{n}^{p}=C_{n-1}^{p-1}+C_{n-1}^{p}\).

Démonstration

Relation de Pascal. On fixe un élément \(a\) de \(E\). Les parties à \(p\) éléments contenant \(a\) sont au nombre de \(C_{n-1}^{p-1}\) (on complète \(a\) par \(p-1\) éléments parmi les \(n-1\) autres) ; celles ne contenant pas \(a\) sont au nombre de \(C_{n-1}^{p}\). Ces deux cas forment une partition, d’où le résultat.

Triangle de Pascal

La relation de Pascal permet de calculer les \(C_{n}^{p}\) ligne par ligne : chaque nombre est la somme de celui qui est au-dessus et de celui qui est au-dessus à gauche.

\(n\) / \(p\)0123456
01
111
2121
31331
414641
515101051
61615201561

Application 10

1) Calculer \(C_{8}^{3}\), \(C_{10}^{8}\), \(C_{12}^{1}\) et \(C_{7}^{4}\).

2) Résoudre dans \(\mathbb{N}\) l’équation \(C_{n}^{2}=45\).

3) Montrer que pour \(1\le p\le n\) : \(pC_{n}^{p}=nC_{n-1}^{p-1}\).

Solution :

1)

\(C_{8}^{3}=\frac{8\times7\times6}{3\times2\times1}=56\) ; \(C_{10}^{8}=C_{10}^{2}=45\) ; \(C_{12}^{1}=12\) ; \(C_{7}^{4}=C_{7}^{3}=35\).

2)

Pour \(n\ge2\) : \(\frac{n(n-1)}{2}=45\iff n^{2}-n-90=0\iff(n-10)(n+9)=0\), donc \(n=10\).

3)

\(pC_{n}^{p}=\frac{p\times n!}{p!\,(n-p)!}=\frac{n\times(n-1)!}{(p-1)!\,(n-p)!}=nC_{n-1}^{p-1}\), car \((n-1)-(p-1)=n-p\).

Application 11

Un club compte \(12\) membres : \(7\) garçons et \(5\) filles. On forme un comité de \(4\) personnes.

1) Combien de comités différents peut-on former ?

2) Combien de comités comportent exactement \(2\) filles ?

3) Combien de comités comportent au moins une fille ?

4) Combien de comités comportent au plus une fille ?

Solution :

1)

Un comité est une partie à \(4\) éléments : \(C_{12}^{4}=\frac{12\times11\times10\times9}{24}=495\).

2)

On choisit \(2\) filles parmi \(5\) et \(2\) garçons parmi \(7\) : \(C_{5}^{2}\times C_{7}^{2}=10\times21=210\).

3)

Complémentaire « aucune fille » : \(C_{7}^{4}=35\). Donc \(495-35=460\).

4)

Aucune fille ou exactement une : \(C_{7}^{4}+C_{5}^{1}\times C_{7}^{3}=35+5\times35=210\).

Application 12

1) On place \(n\) points (\(n\ge3\)) dans le plan, trois d’entre eux n’étant jamais alignés. Combien de segments et combien de triangles ont pour sommets ces points ?

2) Montrer qu’un polygone convexe à \(n\) côtés a \(\frac{n(n-3)}{2}\) diagonales. Combien un décagone a-t-il de diagonales ?

3) Sur un quadrillage, on va du point \(O(0;0)\) au point \(B(5;3)\) par des pas d’une unité vers la droite ou vers le haut. Combien de chemins existe-t-il ?

Solution :

1)

Un segment est une partie à \(2\) points : \(C_{n}^{2}=\frac{n(n-1)}{2}\). Un triangle est une partie à \(3\) points : \(C_{n}^{3}=\frac{n(n-1)(n-2)}{6}\).

2)

Les segments joignant deux sommets sont \(C_{n}^{2}\) ; parmi eux, \(n\) sont des côtés. Diagonales : \(\frac{n(n-1)}{2}-n=\frac{n(n-3)}{2}\). Décagone : \(\frac{10\times7}{2}=35\).

3)

Un chemin comporte \(8\) pas, dont \(3\) vers le haut ; il est déterminé par le choix des positions de ces \(3\) pas parmi \(8\) : \(C_{8}^{3}=56\) chemins.

1. Formule du binôme de Newton

Propriété

Pour tous réels \(a\) et \(b\) et tout entier \(n\ge1\) :

\(\displaystyle (a+b)^{n}=\sum_{k=0}^{n}{C_{n}^{k}a^{n-k}b^{k}}=a^{n}+C_{n}^{1}a^{n-1}b+C_{n}^{2}a^{n-2}b^{2}+\ldots+C_{n}^{n-1}ab^{n-1}+b^{n}\)

Démonstration

En développant \((a+b)^{n}=(a+b)(a+b)\cdots(a+b)\), on obtient le terme \(a^{n-k}b^{k}\) chaque fois qu’on choisit \(b\) dans \(k\) des \(n\) facteurs et \(a\) dans les autres : il y a \(C_{n}^{k}\) tels choix. (On peut aussi raisonner par récurrence avec la relation de Pascal.)

Conséquences

✓ \(\sum_{k=0}^{n}{C_{n}^{k}}=2^{n}\) (avec \(a=b=1\)) : on retrouve le nombre de parties d’un ensemble à \(n\) éléments.

✓ \(\sum_{k=0}^{n}{(-1)^{k}C_{n}^{k}}=0\) pour \(n\ge1\) (avec \(a=1\), \(b=-1\)).

Application 13

1) Développer \((x+2)^{5}\) et \((1-x)^{4}\).

2) Déterminer le coefficient de \(x^{3}\) dans le développement de \((2x-1)^{6}\).

3) Calculer \(\sum_{k=0}^{n}{C_{n}^{k}2^{k}}\) et \(C_{6}^{0}+C_{6}^{2}+C_{6}^{4}+C_{6}^{6}\).

Solution :

1)

Avec la ligne \(5\) du triangle de Pascal : \((x+2)^{5}=x^{5}+10x^{4}+40x^{3}+80x^{2}+80x+32\). Avec la ligne \(4\) : \((1-x)^{4}=1-4x+6x^{2}-4x^{3}+x^{4}\).

2)

Le terme en \(x^{3}\) est \(C_{6}^{3}(2x)^{3}(-1)^{3}=20\times8\times(-1)x^{3}\) : le coefficient est \(-160\).

3)

\(\sum_{k=0}^{n}{C_{n}^{k}2^{k}}=(1+2)^{n}=3^{n}\). Ensuite \(\sum_{k=0}^{6}{C_{6}^{k}}=64\) et \(\sum_{k=0}^{6}{(-1)^{k}C_{6}^{k}}=0\) ; en additionnant, les termes d’indice impair s’éliminent : \(2(C_{6}^{0}+C_{6}^{2}+C_{6}^{4}+C_{6}^{6})=64\), d’où la somme vaut \(32\) (\(1+15+15+1\)).

Application 14

1) En dérivant la fonction \(x\mapsto(1+x)^{n}\) de deux façons, montrer que \(\sum_{k=1}^{n}{kC_{n}^{k}}=n2^{n-1}\).

2) Retrouver ce résultat avec la relation \(kC_{n}^{k}=nC_{n-1}^{k-1}\) de l’application 10.

Solution :

1)

\((1+x)^{n}=\sum_{k=0}^{n}{C_{n}^{k}x^{k}}\). En dérivant : \(n(1+x)^{n-1}=\sum_{k=1}^{n}{kC_{n}^{k}x^{k-1}}\), puis avec \(x=1\) : \(n2^{n-1}=\sum_{k=1}^{n}{kC_{n}^{k}}\).

2)

\(\sum_{k=1}^{n}{kC_{n}^{k}}=n\sum_{k=1}^{n}{C_{n-1}^{k-1}}=n\sum_{j=0}^{n-1}{C_{n-1}^{j}}=n2^{n-1}\).

V. Modèles de tirages

Les trois types de tirages

Une urne contient \(n\) boules discernables ; on tire \(p\) boules.

Type de tirageOrdreRépétitionModèleNombre de tirages
simultanénonnoncombinaison\(C_{n}^{p}\)
successif sans remiseouinonarrangement\(A_{n}^{p}\)
successif avec remiseouioui\(p\)-liste\(n^{p}\)

Application 15

Une urne contient \(10\) boules : \(5\) rouges, \(3\) blanches et \(2\) vertes. On tire simultanément \(3\) boules.

1) Combien y a-t-il de tirages possibles ?

2) Combien de tirages donnent trois boules de même couleur ?

3) Combien donnent exactement deux boules rouges ? une boule de chaque couleur ?

4) Combien donnent au moins une boule verte ?

Solution :

1)

\(C_{10}^{3}=120\).

2)

Trois rouges ou trois blanches (il n’y a que deux vertes) : \(C_{5}^{3}+C_{3}^{3}=10+1=11\).

3)

Deux rouges et une non rouge : \(C_{5}^{2}\times C_{5}^{1}=50\). Une de chaque couleur : \(5\times3\times2=30\).

4)

Complémentaire « aucune verte » : \(C_{8}^{3}=56\), d’où \(120-56=64\).

Application 16

On reprend l’urne de l’application précédente et on tire \(3\) boules l’une après l’autre.

1) Sans remise : combien de tirages possibles ? combien donnent trois boules rouges ? exactement deux boules rouges ?

2) Avec remise : combien de tirages possibles ? combien donnent trois boules rouges ? exactement deux boules rouges ?

Solution :

1)

\(A_{10}^{3}=720\) tirages ; trois rouges : \(A_{5}^{3}=60\). Exactement deux rouges : on choisit la place de la boule non rouge (\(3\) façons), puis on remplit dans l’ordre : \(3\times(5\times4\times5)=300\).

2)

\(10^{3}=1000\) tirages ; trois rouges : \(5^{3}=125\) ; exactement deux rouges : \(3\times5\times5\times5=375\).

Remarque

Dans un tirage successif, il ne faut pas oublier de compter les différentes places possibles des boules (ici le facteur \(3=C_{3}^{1}\)).

1. Permutations avec répétition

Propriété

Le nombre de façons d’aligner \(n\) objets dont \(n_{1}\) sont identiques entre eux, \(n_{2}\) identiques entre eux, …, \(n_{k}\) identiques entre eux (\(n_{1}+n_{2}+\ldots+n_{k}=n\)) est :

\[\frac{n!}{n_{1}!\,n_{2}!\cdots n_{k}!}\]

En particulier, le nombre de mots formés de \(p\) lettres \(a\) et \(n-p\) lettres \(b\) est \(\frac{n!}{p!\,(n-p)!}=C_{n}^{p}\).

Application 17

1) Combien d’anagrammes (mots ayant ou non un sens) peut-on former avec les lettres de « MAROC » ? de « RABAT » ? de « BACCALAUREAT » ?

2) De combien de façons peut-on aligner \(3\) boules rouges identiques et \(2\) boules vertes identiques ?

3) Combien d’anagrammes de « RABAT » commencent par la lettre \(A\) ?

Solution :

1)

MAROC : \(5\) lettres distinctes, \(5!=120\). RABAT : la lettre \(A\) apparaît deux fois, \(\frac{5!}{2!}=60\). BACCALAUREAT : \(12\) lettres dont \(4\) fois \(A\) et \(2\) fois \(C\), les autres distinctes : \(\frac{12!}{4!\,2!}=9979200\).

2)

\(\frac{5!}{3!\,2!}=10=C_{5}^{2}\) (on choisit les places des deux vertes).

3)

Après le \(A\) initial, on range les lettres \(R\), \(B\), \(A\), \(T\) (distinctes) : \(4!=24\).

Méthode

Pour choisir le bon outil, on se pose deux questions : l’ordre compte-t-il ? et les répétitions sont-elles possibles ? Ordre et répétition : \(p\)-listes ; ordre sans répétition : arrangements ; ni ordre ni répétition : combinaisons.

Exercices corrigés تمارين محلولة 12
Exercice 1

Sondage

Facile

On interroge \(100\) personnes sur deux journaux \(A\) et \(B\) : \(45\) lisent \(A\), \(38\) lisent \(B\) et \(15\) lisent les deux.

1) Combien de personnes lisent au moins un des deux journaux ? aucun ?

2) Combien lisent exactement un des deux journaux ?

Afficher la correctionMasquer la correction

1)

\(\mathrm{card}(A\cup B)=45+38-15=68\) ; aucun : \(100-68=32\).

2)

Seulement \(A\) : \(45-15=30\) ; seulement \(B\) : \(38-15=23\) ; exactement un : \(30+23=53\) (ou \(68-15\)).

Exercice 2

Codes d’accès

Facile

Le code d’une porte est formé de \(3\) chiffres (de \(0\) à \(9\)) suivis d’une lettre parmi \(A\), \(B\), \(C\).

1) Combien de codes différents existe-t-il ?

2) Combien de codes ont trois chiffres distincts ?

3) Combien de codes contiennent au moins une fois le chiffre \(0\) ?

Afficher la correctionMasquer la correction

1)

Principe multiplicatif : \(10^{3}\times3=3000\) codes.

2)

\(A_{10}^{3}\times3=720\times3=2160\).

3)

Sans \(0\) : \(9^{3}\times3=2187\). Donc \(3000-2187=813\) codes.

Exercice 3

Calculs et équations

Facile

1) Calculer \(C_{9}^{4}\), \(A_{6}^{3}\) et \(\frac{10!}{8!\,2!}\).

2) Résoudre dans \(\mathbb{N}\) : \(C_{n}^{3}=2C_{n}^{2}\).

3) Montrer que pour tout \(n\ge1\) : \(C_{n}^{2}+C_{n+1}^{2}=n^{2}\).

Afficher la correctionMasquer la correction

1)

\(C_{9}^{4}=\frac{9\times8\times7\times6}{24}=126\) ; \(A_{6}^{3}=6\times5\times4=120\) ; \(\frac{10!}{8!\,2!}=C_{10}^{2}=45\).

2)

Pour \(n\ge3\) : \(\frac{n(n-1)(n-2)}{6}=n(n-1)\iff\frac{n-2}{6}=1\iff n=8\) (on a divisé par \(n(n-1)\ne0\)).

3)

\(C_{n}^{2}+C_{n+1}^{2}=\frac{n(n-1)}{2}+\frac{(n+1)n}{2}=\frac{n(n-1+n+1)}{2}=n^{2}\) (pour \(n=1\) : \(0+1=1\)).

Exercice 4

Course et podium

Facile

Huit coureurs participent à une course (pas d’ex æquo).

1) Combien y a-t-il d’ordres d’arrivée possibles ?

2) Combien de podiums (premier, deuxième, troisième) sont possibles ?

3) Combien de podiums contiennent le coureur Karim ?

Afficher la correctionMasquer la correction

1)

Ce sont les permutations des \(8\) coureurs : \(8!=40320\).

2)

\(A_{8}^{3}=8\times7\times6=336\).

3)

Karim occupe une des \(3\) places, puis on complète les deux autres places dans l’ordre parmi \(7\) coureurs : \(3\times A_{7}^{2}=3\times42=126\).

Exercice 5

Tirage simultané

Moyen

Une urne contient \(4\) boules blanches et \(6\) boules noires. On tire simultanément \(3\) boules.

1) Combien y a-t-il de tirages possibles ?

2) Combien de tirages contiennent exactement une boule blanche ?

3) Combien contiennent au moins une boule blanche ?

4) Combien contiennent des boules de même couleur ?

Afficher la correctionMasquer la correction

1)

\(C_{10}^{3}=120\).

2)

\(C_{4}^{1}\times C_{6}^{2}=4\times15=60\).

3)

Aucune blanche : \(C_{6}^{3}=20\), d’où \(120-20=100\).

4)

\(C_{4}^{3}+C_{6}^{3}=4+20=24\).

Exercice 6

Tirages successifs

Moyen

Une urne contient \(3\) boules rouges et \(4\) boules bleues. On tire successivement deux boules.

1) Sans remise : combien de tirages possibles ? combien donnent deux boules de même couleur ? combien donnent une rouge puis une bleue ? deux boules de couleurs différentes ?

2) Mêmes questions avec remise.

Afficher la correctionMasquer la correction

1)

\(A_{7}^{2}=42\) ; même couleur : \(A_{3}^{2}+A_{4}^{2}=6+12=18\) ; rouge puis bleue : \(3\times4=12\) ; couleurs différentes : \(12+12=24\) (ou \(42-18\)).

2)

\(7^{2}=49\) ; même couleur : \(3^{2}+4^{2}=25\) ; rouge puis bleue : \(12\) ; couleurs différentes : \(24\).

Exercice 7

Jeu de cartes

Moyen

Un jeu de \(32\) cartes comporte \(4\) couleurs (cœur, carreau, trèfle, pique) de \(8\) cartes chacune, dont un as par couleur. Une « main » est un ensemble de \(5\) cartes.

1) Combien y a-t-il de mains ?

2) Combien de mains contiennent exactement deux as ?

3) Combien contiennent au moins un cœur ?

4) Combien sont formées de cartes d’une même couleur ?

Afficher la correctionMasquer la correction

1)

\(C_{32}^{5}=201376\).

2)

\(C_{4}^{2}\times C_{28}^{3}=6\times3276=19656\).

3)

Sans cœur : \(C_{24}^{5}=42504\) ; donc \(201376-42504=158872\).

4)

On choisit la couleur (\(4\) façons) puis \(5\) cartes parmi \(8\) : \(4\times C_{8}^{5}=4\times56=224\).

Exercice 8

Binôme de Newton

Moyen

1) Développer \((1+\sqrt{2})^{4}\) et \((1-\sqrt{2})^{4}\). En déduire que \((1+\sqrt{2})^{4}+(1-\sqrt{2})^{4}\) est un entier.

2) Déterminer le coefficient de \(x^{4}\) dans le développement de \((x^{2}-\frac{2}{x})^{8}\) (\(x\ne0\)). Ce développement contient-il un terme constant ?

Afficher la correctionMasquer la correction

1)

\((1+\sqrt{2})^{4}=1+4\sqrt{2}+6\times2+4\times2\sqrt{2}+4=17+12\sqrt{2}\) et de même \((1-\sqrt{2})^{4}=17-12\sqrt{2}\). La somme vaut \(34\).

2)

Le terme général est \(C_{8}^{k}(x^{2})^{8-k}(-\frac{2}{x})^{k}=C_{8}^{k}(-2)^{k}x^{16-3k}\). Pour \(16-3k=4\) : \(k=4\), coefficient \(C_{8}^{4}\times16=70\times16=1120\). Un terme constant exigerait \(16-3k=0\), impossible pour \(k\) entier : il n’y en a pas.

Exercice 9

Anagrammes et chemins

Moyen

1) Combien d’anagrammes du mot « PARALLELE » peut-on former ?

2) Sur un quadrillage, on va de \(O(0;0)\) à \(B(4;4)\) par des pas d’une unité vers la droite ou vers le haut. Combien y a-t-il de chemins ? Combien passent par le point \(C(2;2)\) ?

3) Combien de rectangles (de côtés portés par les lignes) peut-on voir sur un échiquier de \(8\times8\) cases ?

Afficher la correctionMasquer la correction

1)

\(9\) lettres : \(A\) deux fois, \(L\) trois fois, \(E\) deux fois, \(P\) et \(R\) une fois : \(\frac{9!}{2!\,3!\,2!}=\frac{362880}{24}=15120\).

2)

Un chemin compte \(8\) pas dont \(4\) vers le haut : \(C_{8}^{4}=70\). Par \(C\) : \(C_{4}^{2}\) chemins de \(O\) à \(C\), puis \(C_{4}^{2}\) de \(C\) à \(B\) : \(6\times6=36\).

3)

L’échiquier est délimité par \(9\) lignes horizontales et \(9\) verticales. Un rectangle est déterminé par le choix de \(2\) lignes horizontales et de \(2\) lignes verticales : \(C_{9}^{2}\times C_{9}^{2}=36\times36=1296\).

Exercice 10

Une identité de Vandermonde

Difficile

Soit \(n\in\mathbb{N}^{*}\). Un groupe est formé de \(n\) garçons et \(n\) filles ; on choisit un comité de \(n\) personnes.

1) Combien de comités peut-on former ?

2) Combien de comités contiennent exactement \(k\) filles (\(0\le k\le n\)) ?

3) En déduire que \(\sum_{k=0}^{n}{(C_{n}^{k})^{2}}=C_{2n}^{n}\), et vérifier pour \(n=3\).

Afficher la correctionMasquer la correction

1)

\(C_{2n}^{n}\).

2)

\(k\) filles parmi \(n\) et \(n-k\) garçons parmi \(n\) : \(C_{n}^{k}\times C_{n}^{n-k}=(C_{n}^{k})^{2}\) (car \(C_{n}^{n-k}=C_{n}^{k}\)).

3)

Les comités à \(0\), \(1\), …, \(n\) filles forment une partition de l’ensemble des comités : \(\sum_{k=0}^{n}{(C_{n}^{k})^{2}}=C_{2n}^{n}\). Pour \(n=3\) : \(1+9+9+1=20=C_{6}^{3}\).

Exercice 11

Surjections et applications croissantes

Difficile

Soient \(E=\{1;2;3;4\}\) et \(F=\{a;b;c\}\).

1) Combien y a-t-il d’applications de \(E\) vers \(F\) ? Combien ne prennent pas la valeur \(a\) ?

2) En utilisant le complémentaire, montrer que le nombre de surjections de \(E\) sur \(F\) est \(3^{4}-3\times2^{4}+3=36\).

3) Retrouver ce nombre directement : une surjection a exactement un élément de \(F\) ayant deux antécédents.

4) Combien y a-t-il d’applications strictement croissantes de \(\{1;2;3\}\) vers \(\{1;2;3;4;5;6\}\) ?

Afficher la correctionMasquer la correction

1)

\(3^{4}=81\) applications ; sans la valeur \(a\) : applications vers \(\{b;c\}\), soit \(2^{4}=16\).

2)

Soient \(N_{a}\), \(N_{b}\), \(N_{c}\) les ensembles d’applications qui ne prennent pas la valeur \(a\), \(b\), \(c\). Chacun a \(16\) éléments ; l’intersection de deux d’entre eux contient une seule application (constante), et \(N_{a}\cap N_{b}\cap N_{c}=\varnothing\). Le nombre d’applications non surjectives est \(\mathrm{card}(N_{a}\cup N_{b}\cup N_{c})=3\times16-3\times1+0=45\), d’où \(81-45=36\) surjections.

3)

Choix de l’élément de \(F\) ayant deux antécédents : \(3\) ; choix de ces deux antécédents : \(C_{4}^{2}=6\) ; les deux éléments restants de \(E\) sont envoyés bijectivement sur les deux autres éléments de \(F\) : \(2!\). Total : \(3\times6\times2=36\).

4)

Une application strictement croissante est déterminée par l’ensemble de ses \(3\) valeurs (rangées ensuite dans l’ordre croissant) : \(C_{6}^{3}=20\).

Exercice 12

Coefficients binomiaux : variations et sommes

Difficile

Soit \(n\in\mathbb{N}^{*}\).

1) Montrer que pour \(0\le k\le n-1\) : \(\frac{C_{n}^{k+1}}{C_{n}^{k}}=\frac{n-k}{k+1}\). En déduire, pour \(n=10\), la plus grande des valeurs \(C_{10}^{k}\).

2) Montrer que pour \(0\le k\le n\) : \(\frac{C_{n}^{k}}{k+1}=\frac{C_{n+1}^{k+1}}{n+1}\).

3) En déduire \(\sum_{k=0}^{n}{\frac{C_{n}^{k}}{k+1}}=\frac{2^{n+1}-1}{n+1}\), et vérifier pour \(n=2\).

Afficher la correctionMasquer la correction

1)

\(\frac{C_{n}^{k+1}}{C_{n}^{k}}=\frac{n!}{(k+1)!\,(n-k-1)!}\times\frac{k!\,(n-k)!}{n!}=\frac{n-k}{k+1}\). Ce quotient est \(\ge1\) si et seulement si \(n-k\ge k+1\), soit \(k\le\frac{n-1}{2}\). Pour \(n=10\) : \(C_{10}^{k}\) croît pour \(k\le5\) puis décroît ; le maximum est \(C_{10}^{5}=252\).

2)

\(\frac{C_{n+1}^{k+1}}{n+1}=\frac{(n+1)!}{(n+1)(k+1)!\,(n-k)!}=\frac{n!}{(k+1)\,k!\,(n-k)!}=\frac{C_{n}^{k}}{k+1}\).

3)

\(\sum_{k=0}^{n}{\frac{C_{n}^{k}}{k+1}}=\frac{1}{n+1}\sum_{j=1}^{n+1}{C_{n+1}^{j}}=\frac{2^{n+1}-C_{n+1}^{0}}{n+1}=\frac{2^{n+1}-1}{n+1}\). Pour \(n=2\) : \(1+1+\frac{1}{3}=\frac{7}{3}=\frac{2^{3}-1}{3}\).