Exercices corrigés : dénombrement (201-SN1-RE)

$7!=7\times 6\times 5\times 4\times 3\times 2\times 1=5040$.

$10!=10\times 9\times 8\times 7!$, donc $\dfrac{10!}{7!}=10\times 9\times 8=720$.

Piège : calculer $10!=3\,628\,800$ et $7!=5040$ séparément, puis diviser. Le résultat est le même, mais avec deux grands nombres à recopier sans erreur.

$A(8,\,3)=\dfrac{8!}{5!}=8\times 7\times 6=336$.

Lecture : trois places ORDONNÉES, 8 choix pour la première, 7 pour la deuxième, 6 pour la troisième.

$\dbinom{10}{4}=\dfrac{10\times 9\times 8\times 7}{4\times 3\times 2\times 1}=\dfrac{5040}{24}=210$.

Les $5040$ arrangements de 4 objets parmi 10 sont regroupés par paquets de $4!=24$ qui contiennent les mêmes objets : chaque paquet est une seule combinaison.

Par symétrie, $\dbinom{12}{10}=\dbinom{12}{2}=\dfrac{12\times 11}{2}=66$.

Garder 10 objets parmi 12, c'est exactement décider lesquels 2 on laisse : les deux choix se correspondent un à un.

$(n+1)!=(n+1)\times n\times(n-1)!$, donc $\dfrac{(n+1)!}{(n-1)!}=(n+1)\,n$.

Pour $n=9$ : $10\times 9=90$.

Cinq places, quatre choix à chacune, et le choix d'une place ne réduit pas les suivantes : $4^{5}=1024$.

Piège : écrire $A(4,\,5)$. Il n'existe aucun arrangement de 5 objets distincts parmi 4 ; ici les bases peuvent revenir, c'est une suite avec répétition.

Si les 8 objets étaient tous distincts, il y aurait $8!=40\,320$ rangements.

Échanger entre eux les 3 objets identiques ne change pas le rangement ($3!=6$ façons), échanger les 2 autres non plus ($2!=2$ façons) : chaque rangement visible a été compté $6\times 2=12$ fois.

$\dfrac{8!}{3!\,2!}=\dfrac{40\,320}{12}=3360$.

$\dbinom{6}{2}=15$ et $\dbinom{4}{1}=4$ : deux choix faits l'un après l'autre se multiplient, $15\times 4=60$.

Le terme en $x^{3}$ de $(1+x)^{7}$ est $\dbinom{7}{3}\,1^{4}\,x^{3}$, donc le coefficient vaut $\dbinom{7}{3}=\dfrac{7\times 6\times 5}{6}=35$.

$\dbinom{n}{2}=\dfrac{n(n-1)}{2}=45$ donne $n(n-1)=90=10\times 9$, donc $n=10$.

L'équation $n^{2}-n-90=0$ a aussi la racine $n=-9$, rejetée : $n$ est un nombre d'objets.

Formule d'inclusion-exclusion : $|A\cup B|=|A|+|B|-|A\cap B|=25+18-7=36$.

Les 7 éléments communs appartiennent aux deux ensembles : la somme $25+18$ les compte deux fois, on les retire une fois.

Un code se construit en quatre étapes : la lettre (8 choix), puis le premier chiffre (10 choix), le deuxième (10), le troisième (10).

Le nombre de choix d'une étape ne dépend pas des choix précédents : le principe de multiplication s'applique.

$8\times 10\times 10\times 10=8000$ codes.

Les chiffres doivent être distincts : 10 choix pour le premier, 9 pour le deuxième (tout sauf le premier), 8 pour le troisième.

$8\times 10\times 9\times 8=5760$ codes acceptés.

Le NOMBRE de choix de chaque étape reste fixe, même si la LISTE des choix dépend des étapes précédentes : c'est tout ce que demande le principe de multiplication.

« Au moins un 0 » réunit trois cas (un, deux ou trois zéros) : on passe par le contraire, « aucun 0 ».

Codes sans aucun 0 : $8\times 9\times 9\times 9=8\times 729=5832$.

Codes avec au moins un 0 : $8000-5832=2168$.

Le calcul $8\times 3\times 100$ fabrique C400 deux fois : en choisissant le 0 de la deuxième place puis « 0 » pour la troisième, et en choisissant le 0 de la troisième place puis « 0 » pour la deuxième. Il fabrique C000 trois fois, une par place choisie.

Pour une station, chaque événement $Z_{i}$ contient $10\times 10=100$ codes, chaque intersection $Z_{i}\cap Z_{j}$ en contient $10$, et $Z_{1}\cap Z_{2}\cap Z_{3}$ un seul.

$|Z_{1}\cup Z_{2}\cup Z_{3}|=3\times 100-3\times 10+1=271$.

Vérification : $8\times 271=2168$, le résultat du c). Le diagramme du corrigé montre les huit régions : $3\times 81+3\times 9+1=271$ et $729$ codes sans 0.

Piège : $300$ n'est pas faux par hasard, il pèse chaque code par son nombre de zéros, $243\times 1+27\times 2+1\times 3=300$. Compter, c'est compter chaque code UNE fois.

Un code de station a un chiffre en deuxième position, un code de blanc a la lettre L : aucune étiquette n'est dans les deux familles, même BL07 et B407.

Les deux familles sont disjointes, le principe d'addition s'applique : $8000+100=8100$ étiquettes.

Le principe d'addition n'exige pas que les familles « se ressemblent peu », il exige qu'elles n'aient AUCUN élément commun ; c'est ce qu'il fallait vérifier.

Avec $k$ chiffres, il y a $8\times 10^{k}$ codes. Il en faut au moins $25\,000$ : $10^{k}\ge 3125$.

$k=3$ donne $8000$ codes, insuffisant ; $k=4$ donne $80\,000$ codes. Le plus petit nombre de chiffres est $4$.

Un chiffre de plus multiplie la capacité par 10, ce qui laisse de la marge pour les années suivantes.

Les neuf flacons sont distincts et tous placés : c'est une permutation de 9 objets.

9 choix pour la position 1, 8 pour la position 2, et ainsi de suite : $9!=362\,880$ ordres.

La position 1 est imposée. Il reste à ranger les 8 autres flacons dans les positions 2 à 9 : $8!=40\,320$ ordres.

On colle E1 et E2 en un seul bloc. Après le blanc, il reste 7 objets à ranger : le bloc et les 6 extraits, soit $7!=5040$ rangements.

À l'intérieur du bloc, deux ordres : E1E2 ou E2E1. Total : $2\times 7!=10\,080$ ordres.

Le corrigé montre un de ces ordres : le bloc occupe les positions 4 et 5.

Piège : oublier le facteur 2 du bloc, ou ranger 8 objets au lieu de 7. Le bloc REMPLACE deux flacons, il ne s'y ajoute pas.

Les ordres du b) se partagent en deux familles disjointes : étalons voisins ou non. Par le contraire :

$40\,320-10\,080=30\,240$ ordres où les étalons ne sont pas voisins.

Compter directement les positions non voisines est possible mais plus long ; le contraire évite d'oublier un cas.

Échanger les étiquettes E1 et E2 transforme un ordre où E1 passe avant E2 en un ordre où E2 passe avant E1, et inversement.

Cet échange associe les ordres deux à deux, sans en oublier ni en compter deux fois : les deux familles ont donc le même nombre d'éléments.

$\dfrac{8!}{2}=20\,160$ ordres où E1 passe avant E2.

Piège : répondre $10\,080$ comme au c). « Avant » ne veut pas dire « juste avant ».

Les positions sont numérotées : remplir les positions 1 à 4 avec 4 extraits distincts est un arrangement, $A(6,\,4)=6\times 5\times 4\times 3=360$.

Si l'ordre ne comptait pas, on choisirait seulement un groupe de 4 extraits : $\dbinom{6}{4}=15$.

Rapport : $\dfrac{360}{15}=24=4!$. Chaque groupe de 4 extraits se range de $4!$ façons dans les 4 positions : $A(6,\,4)=4!\times\dbinom{6}{4}$.

C'est le lien entre arrangements et combinaisons : on décide d'abord QUELS objets, puis dans QUEL ORDRE.

Les 4 témoins sont identiques : seul compte l'ENSEMBLE des puits choisis, pas l'ordre dans lequel on les choisit. C'est une combinaison.

$\dbinom{24}{4}=\dfrac{24\times 23\times 22\times 21}{4\times 3\times 2\times 1}=\dfrac{255\,024}{24}=10\,626$ choix.

Les souches sont différentes : mettre s1 en A1 et s2 en B3 n'est pas la même chose que l'inverse. C'est un arrangement.

$A(24,\,4)=24\times 23\times 22\times 21=255\,024$ placements.

Rapport : $\dfrac{255\,024}{10\,626}=24=4!$. Chaque choix de 4 puits du a) accueille les 4 souches de $4!$ façons.

Le fil de la série : la même plaque, les mêmes puits, mais deux résultats ne sont « le même » qu'au a). La phrase qui le dit vient avant la formule.

Deux étapes : choisir la rangée (4 façons), puis 4 puits parmi les 6 de cette rangée, $\dbinom{6}{4}=15$ façons.

$4\times 15=60$ choix. Deux rangées différentes donnent des choix différents, et aucun choix n'est dans deux rangées à la fois : rien n'est compté deux fois.

Il y a exactement 4 rangées : 4 puits dans 4 rangées différentes, c'est UN puits par rangée.

Un tel choix est donc décrit par la colonne du puits de A, celle de B, celle de C, celle de D, toutes différentes : $6\times 5\times 4\times 3=A(6,\,4)=360$ choix.

Le corrigé montre l'un d'eux : A2, B5, C1, D4.

Piège : diviser par $4!$ « parce que l'ordre ne compte pas ». Mais on n'a pas ordonné les puits : la rangée est une étiquette qui distingue déjà les 4 puits, et chaque ensemble de 4 puits n'est produit qu'une fois.

« Au moins un » : on passe par le contraire, « aucun puits dans la rangée A », soit 4 puits pris parmi les 18 des rangées B, C et D.

$\dbinom{18}{4}=\dfrac{18\times 17\times 16\times 15}{24}=3060$, donc $10\,626-3060=7566$ choix.

Piège : choisir d'abord « le » puits de la rangée A (6 façons), puis 3 autres parmi 23. Ce calcul compte deux fois un choix qui a deux puits dans la rangée A : il n'y a pas de puits « désigné ».

Hors du bord : rangées B et C, colonnes 2 à 5, soit $2\times 4=8$ puits.

$\dbinom{8}{4}=\dfrac{8\times 7\times 6\times 5}{24}=70$ choix.

Ce plan protège les témoins, au prix de beaucoup moins de choix : $70$ contre $10\,626$.

« Éphémères » se traduit par $E$, « pas de plécoptères » par le complémentaire $\overline{P}$, et « mais » par une intersection : $E\cap\overline{P}$.

Les stations de $E$ se partagent en celles qui sont dans $P$ et celles qui n'y sont pas : $|E\cap\overline{P}|=|E|-|E\cap P|=52-24=28$.

$=52+31+45-24-33-19+15=67$ stations.

Pourquoi le $+15$ : une station du cœur est comptée 3 fois dans la première somme, puis retirée 3 fois avec les intersections. Il faut la rajouter une fois pour qu'elle compte exactement une fois.

$80-67=13$ stations sans aucun des trois groupes.

« Aucun groupe » est le complémentaire de « au moins un groupe » : $\overline{E\cup P\cup T}$. Par la loi de De Morgan, c'est aussi « ni $E$, ni $P$, ni $T$ » : $\overline{E}\cap\overline{P}\cap\overline{T}$.

Ces stations sont à l'extérieur des trois cercles, dans le rectangle des 80 stations.

On part du cœur, $|E\cap P\cap T|=15$, puis on retire le cœur de chaque intersection deux à deux :

$E\cap P$ seulement : $24-15=9$ ; $E\cap T$ seulement : $33-15=18$ ; $P\cap T$ seulement : $19-15=4$.

Puis chaque groupe seul : $E$ seul $52-9-18-15=10$ ; $P$ seul $31-9-4-15=3$ ; $T$ seul $45-18-4-15=8$.

Un seul groupe : $10+3+8=21$ stations.

Vérification : $10+3+8+9+18+4+15=67$, le résultat du b).

Exactement deux groupes : $9+18+4=31$ stations. Les 80 stations sont équiprobables, donc $P=\dfrac{31}{80}=0{,}3875$.

Piège : prendre $24+33+19=76$ stations. Ces trois intersections contiennent toutes les 15 stations du cœur, qui ont TROIS groupes.

Dans la somme $|E|+|P|+|T|$, une station est comptée une fois pour chaque ensemble qui la contient.

Les 21 stations à un groupe comptent 1 fois, les 31 à deux groupes 2 fois, les 15 à trois groupes 3 fois, les 13 sans groupe 0 fois :

$21\times 1+31\times 2+15\times 3=21+62+45=128$.

Le total 128 n'est donc pas un nombre de stations, et il n'a aucune raison d'être inférieur à 80 : les données sont cohérentes.

Chaque nombre intérieur de la ligne 7 est la somme des deux nombres placés au-dessus de lui dans la ligne 6, et chaque ligne commence et finit par $1$ :

$1$ ; $1+6=7$ ; $6+15=21$ ; $15+20=35$ ; $20+15=35$ ; $15+6=21$ ; $6+1=7$ ; $1$.

Donc $\binom{7}{3}=\binom{6}{2}+\binom{6}{3}=15+20=35$, ce que confirme $\dfrac{7\times 6\times 5}{3!}=35$.

La ligne se lit pareil dans les deux sens : c'est la symétrie $\binom{n}{k}=\binom{n}{n-k}$, un contrôle gratuit.

La ligne 4 est $1,\ 4,\ 6,\ 4,\ 1$ :

$(a+b)^{4}=a^{4}+4a^{3}b+6a^{2}b^{2}+4ab^{3}+b^{4}$.

Le coefficient de $a^{2}b^{2}$ est $\binom{4}{2}=6$ : parmi les 4 facteurs $(a+b)$, on choisit les 2 qui fournissent $b$.

On applique le binôme avec $a=2x$ et $b=-1$. Le terme général est $\binom{5}{k}(2x)^{5-k}(-1)^{k}$.

$x^{3}$ apparaît pour $5-k=3$, soit $k=2$ : $\binom{5}{2}(2x)^{3}(-1)^{2}=10\times 8x^{3}\times 1=80x^{3}$.

Le coefficient vaut $80$.

Piège : écrire $10x^{3}$ ou $20x^{3}$ en oubliant que le $2$ est élevé à la puissance avec $x$ : $(2x)^{3}=8x^{3}$, pas $2x^{3}$.

$x^{2}$ apparaît pour $5-k=2$, soit $k=3$ : $\binom{5}{3}(2x)^{2}(-1)^{3}=10\times 4x^{2}\times(-1)=-40x^{2}$.

Le coefficient vaut $-40$.

Piège : perdre le signe. Le $-1$ fait partie du terme du binôme, et $(-1)^{k}$ est négatif pour $k$ impair.

Le terme général est $\binom{6}{k}\left(x^{2}\right)^{6-k}\left(\dfrac{3}{x}\right)^{k}=\binom{6}{k}\,3^{k}\,x^{12-2k-k}=\binom{6}{k}\,3^{k}\,x^{12-3k}$.

Il est indépendant de $x$ quand $12-3k=0$, soit $k=4$ : $\binom{6}{4}\times 3^{4}=15\times 81=1215$.

On vérifie que $k=4$ est bien un entier entre $0$ et $6$ ; sinon, le développement n'aurait pas de terme constant.

Avec $a=b=1$ : $\sum_{k=0}^{7}\binom{7}{k}=(1+1)^{7}=2^{7}=128$.

Avec $a=1$ et $b=-1$ : $\sum_{k=0}^{7}\binom{7}{k}(-1)^{k}=(1-1)^{7}=0$.

Vérification sur la ligne : $1+7+21+35+35+21+7+1=128$, et $1-7+21-35+35-21+7-1=0$.

Les trois premiers termes donnent $1+0{,}2+0{,}018=1{,}218$. La calculatrice donne $(1{,}02)^{10}\approx 1{,}218\,99$, soit $1{,}219$ au millième.

L'écart vient surtout du quatrième terme, $\binom{10}{3}0{,}02^{3}=120\times 0{,}000\,008\approx 0{,}000\,96$ : les termes suivants deviennent vite négligeables parce que $0{,}02$ est petit.

Piège : la croissance « simple » $1+10\times 0{,}02=1{,}2$ oublie les intérêts composés, le terme en $\binom{10}{2}$ : l'effectif augmente de près de $22\,\%$, pas de $20\,\%$.

Chaque spin a 2 orientations, indépendamment des autres : $2^{6}=64$ configurations.

Une configuration à 2 spins vers le haut est déterminée par les POSITIONS de ces 2 spins, choisies parmi 6, sans ordre : $\binom{6}{2}=15$. Son aimantation vaut $M=2\times 2-6=-2$.

Piège : $A(6,\,2)=30$. Choisir « position 1 puis position 4 » ou « position 4 puis position 1 » donne la même configuration.

Une configuration à $k$ spins vers le haut est entièrement déterminée par l'ensemble des positions de ses spins vers le haut, et cet ensemble peut être n'importe quelle partie à $k$ éléments de $\{1,\dots,n\}$. Il y a donc $\binom{n}{k}$ telles configurations.

Avoir exactement $k$ spins vers le haut, c'est avoir exactement $n-k$ spins vers le bas : les deux familles sont la MÊME famille, décrite par ses spins du haut ou par ses spins du bas.

Compter cette famille par les positions des spins vers le bas donne $\binom{n}{n-k}$. Un même ensemble compté de deux façons donne le même nombre : $\binom{n}{k}=\binom{n}{n-k}$.