Exercices corrigés — Combinatoire et dénombrement (Tle spé)

1. Chaque position offre \(10\) choix indépendants. Par le principe multiplicatif : \(10\times10\times10\times10=10^4=10\,000\).

2. On a successivement \(10\), puis \(9\), puis \(8\), puis \(7\) choix : \(10\times9\times8\times7=5\,040\).

3. Le premier chiffre ne peut pas être \(0\) : \(9\) choix. Les trois autres positions ont chacune \(10\) choix, donc \(9\times10^3=9\,000\).

4. Le premier chiffre a \(9\) choix non nuls. Le second a encore \(9\) choix parmi les chiffres restants, puis \(8\), puis \(7\) : \(9\times9\times8\times7=4\,536\).

1. Ranger les \(6\) livres distincts revient à choisir une permutation : \(6!=720\).

2. On considère \(A\) et \(B\) comme un bloc. Il y a alors \(5!\) ordres des cinq objets, et \(2\) ordres internes dans le bloc : \(2\times5!=240\).

3. On compte par complément : \(720-240=480\).

4. L'échange de \(A\) et \(B\) met en bijection les rangements où \(A\) est avant \(B\) et ceux où \(B\) est avant \(A\). Les deux classes ont donc la même taille : \(\dfrac{720}{2}=360\).

1. L'ordre ne compte pas : on choisit une partie à \(4\) éléments parmi \(12\), soit \(\binom{12}{4}=495\).

2. Une place est occupée par \(A\). Il reste à choisir \(3\) élèves parmi les \(11\) autres : \(\binom{11}{3}=165\).

3. On choisit les \(4\) membres parmi les \(11\) élèves autres que \(A\), donc \(\binom{11}{4}=330\).

4. On choisit lequel de \(A\) ou \(B\) est présent : \(2\) choix. Puis on choisit les \(3\) autres membres parmi les \(10\) élèves restants : \(2\binom{10}{3}=240\).

1. Pour chacun des \(5\) éléments, on a deux choix indépendants : présent ou absent. Il y a donc \(2^5=32\) parties.

2. Choisir une partie de cardinal \(3\) revient à choisir \(3\) éléments parmi \(5\) : \(\binom{5}{3}=10\).

3. Il suffit de choisir les \(3\) positions occupées par un \(1\) parmi les \(5\) positions : \(\binom{5}{3}=10\).

4. Une partie de cardinal \(3\) est entièrement déterminée par les trois positions marquées \(1\) dans son mot indicateur, et réciproquement. C'est une bijection.

1. On utilise \(\binom{8}{2}=\dfrac{8\times7}{2}=28\).

2. Par symétrie, \(\binom{8}{6}=\binom{8}{8-6}=\binom{8}{2}=28\).

3. La relation de Pascal donne \(\binom{9}{3}=\binom{8}{3}+\binom{8}{2}=56+28=84\).

4. La somme compte toutes les parties d'un ensemble à \(5\) éléments, classées selon leur cardinal. Elle vaut donc \(2^5=32\).

1. Les rôles sont distincts : \(8\) choix pour le président, puis \(7\), puis \(6\). On obtient \(336\).

2. Sans rôle, l'ordre ne compte pas : \(\binom{8}{3}=56\).

3. Une fois les trois personnes choisies, on peut leur attribuer les trois rôles de \(3!\) façons. Ainsi \(336=6\times56\).

4. On effectue d'abord les \(336\) attributions de rôles, puis on choisit \(2\) personnes parmi les \(5\) restantes : \(336\binom{5}{2}=3360\).

1. On choisit d'abord les \(3\) positions des \(A\), puis parmi les \(4\) positions restantes les \(2\) positions des \(B\). Les deux dernières sont des \(C\). Donc \(35\times6=210\).

2. On choisit les \(3\) positions des \(A\), puis chacune des \(4\) positions restantes peut recevoir \(B\) ou \(C\). Donc \(\binom{7}{3}2^4=560\).

3. Après placement des \(3\) lettres \(A\), il reste \(4\) positions. Le nombre de \(B\) peut être \(2,3\) ou \(4\). On additionne ces cas disjoints : \(35(6+4+1)=385\).

4. Parmi les \(2^4\) remplissages des quatre positions restantes par \(B\) ou \(C\), on retire l'unique remplissage tout en \(C\). Ainsi \(35(16-1)=525\).

1. On part des \(6!\) permutations de six positions, puis on divise par \(2!\) pour l'échange des deux \(A\) et par \(2!\) pour l'échange des deux \(N\) : \(180\).

2. La lettre \(B\) est fixée. On permute les cinq lettres restantes \(A,A,N,N,E\) : \(\dfrac{5!}{2!\,2!}=30\).

3. Après avoir fixé \(B\) au début et \(E\) à la fin, on arrange \(A,A,N,N\), ce qui donne \(\dfrac{4!}{2!\,2!}=6\).

4. On traite \(AA\) comme un bloc. Les cinq objets sont alors \(AA,B,N,N,E\), avec deux \(N\) identiques : \(\dfrac{5!}{2!}=60\).

1. Un chemin minimal est un mot de \(9\) pas contenant \(4\) pas vers le haut (ou \(5\) vers la droite). Il y en a \(\binom{9}{4}=126\).

2. De \(A\) à \(P\), on place \(1\) pas vertical parmi \(3\) pas : \(\binom{3}{1}=3\). De \(P\) à \(B\), il reste \(3\) pas de chaque type : \(\binom{6}{3}=20\). Produit : \(60\).

3. Les chemins passant par \(P\) et ceux l'évitant forment une partition des \(126\) chemins. Le complément vaut \(126-60=66\).

4. On fixe le premier pas \(R\) et le dernier pas \(H\). Il reste \(7\) positions contenant \(4\) pas \(R\) et \(3\) pas \(H\), donc \(\binom{7}{3}=35\).

1. On choisit indépendamment \(2\) filles parmi \(6\) et \(2\) garçons parmi \(5\) : \(15\times10=150\).

2. On compte tous les comités puis on retire ceux composés uniquement de garçons : \(330-5=325\).

3. Avec \(4\) membres et au moins un garçon, les cas possibles sont \(2F,2G\) ou \(3F,1G\). Les cas sont disjoints : \(150+100=250\).

4. La fille \(A\) est fixée. On choisit encore \(2\) filles parmi les \(5\) autres et \(1\) garçon parmi \(5\) : \(10\times5=50\).

1. Les cinq positions sont ordonnées. Les lettres donnent \(8\times7\times6\) possibilités et les chiffres \(10\times9\). Le produit vaut \(30\,240\).

2. On choisit un ensemble de trois lettres : \(\binom{8}{3}=56\), puis un couple ordonné de chiffres distincts : \(90\). Total : \(5040\).

3. La première lettre est fixée. Il reste \(7\) puis \(6\) choix pour les deux autres lettres, et \(10\times9\) pour les chiffres : \(3780\).

4. On compte toutes les suites de trois lettres distinctes et on retire celles qui n'utilisent ni \(A\) ni \(B\), donc formées avec les \(6\) autres lettres. Cela donne \((336-120)\times90=19\,440\).

1. Une permutation de \(8\) objets distincts se compte par \(8!=40\,320\).

2. Les permutations où \(A\) et \(B\) sont adjacents se comptent en formant un bloc : \(2\times7!\). Par complément, \(8!-2\times7!=30\,240\).

3. L'échange de \(A\) et \(B\) conserve la non-adjacence et échange les deux ordres. La moitié des \(30\,240\) permutations convient : \(15\,120\).

4. Les positions de \(A\) et \(B\) doivent être distantes de \(2\). Il existe \(6\) paires de positions \(\{i,i+2\}\), et \(2\) ordres pour \(A,B\), soit \(12\) placements. Les \(6\) autres objets se permutent de \(6!\) façons : \(12\times6!=8640\).

1. Si les positions des \(1\) sont \(i_1\lt\cdots\lt i_5\) avec \(i_{r+1}\ge i_r+2\), poser \(j_r=i_r-(r-1)\). Alors \(1\le j_1\lt\cdots\lt j_5\le8\). Cette transformation est bijective.

2. La bijection précédente ramène le problème au choix de \(5\) positions parmi \(8\), donc \(\binom{8}{5}=56\).

3. Si le premier caractère est \(1\), le deuxième est forcément \(0\). Il reste un mot de longueur \(10\) avec \(4\) chiffres \(1\) non consécutifs, donc \(\binom{10-4+1}{4}=\binom{7}{4}=35\).

4. Les positions \(1\) et \(12\) sont fixées à \(1\), donc les positions \(2\) et \(11\) sont des zéros. Entre les deux, il reste \(8\) places (3 à 10) dans lesquelles placer \(3\) chiffres \(1\) non consécutifs : \(\binom{8-3+1}{3}=\binom{6}{3}=20\).

1. On choisit laquelle de \(A,B\) est présente, puis \(4\) personnes parmi les \(10\) autres : \(2\binom{10}{4}=420\).

2. Après choix de l'unique personne parmi \(A,B\), il reste à sélectionner \(4\) personnes parmi \(10\), avec au moins une de \(C,D\). On retire les choix faits uniquement parmi les \(8\) autres : \(2(210-70)=280\).

3. On choisit une personne parmi \(A,B\) (2 choix), une parmi \(C,D\) (2 choix), puis \(3\) personnes parmi les \(8\) ordinaires : \(4\binom{8}{3}=224\).

4. On choisit l'unique personne parmi \(A,B\), on impose \(C,D\), puis on choisit \(2\) personnes parmi les \(8\) ordinaires : \(2\binom{8}{2}=56\). Les cas 'exactement un de \(C,D\)' et 'les deux' sont disjoints et couvrent 'au moins un', donc \(224+56=280\).

1. Un chemin est un mot de \(10\) pas contenant \(4\) pas verticaux. Il y en a \(\binom{10}{4}=210\).

2. De \(A\) à \(P\), il faut \(3R,2H\) : \(\binom{5}{2}=10\) chemins. De \(P\) à \(B\), il faut encore \(3R,2H\) : \(10\) chemins. Produit : \(100\).

3. Les chemins passant par \(P\) et ceux l'évitant forment une partition. Le complément vaut \(110\).

4. On fixe le premier pas \(R\). Pour atteindre \(P\), il reste \(4\) pas contenant \(2H\), donc \(\binom{4}{2}=6\). De \(P\) à \(B\), il y a \(10\) chemins. Total : \(60\).

1. Par Pascal : \(\binom{13}{5}=\binom{12}{5}+\binom{12}{4}=792+495=1287\).

2. Dans un ensemble à \(n+1\) éléments, fixer un élément \(x\). Une partie à \(k\) éléments soit ne contient pas \(x\), ce qui donne \(\binom{n}{k}\) choix, soit contient \(x\), puis on choisit \(k-1\) éléments parmi les \(n\) autres : \(\binom{n}{k-1}\). Les deux cas sont disjoints et exhaustifs.

3. La relation de Pascal donne \(\binom{14}{5}=\binom{13}{5}+\binom{13}{4}\). Donc la différence demandée vaut \(\binom{13}{5}=1287\).

4. La somme compte toutes les parties d'un ensemble à \(8\) éléments, classées par cardinal. Un ensemble à \(8\) éléments possède \(2^8=256\) parties.

1. Après avoir imposé \(A\), il faut choisir \(3\) éléments parmi les \(9\) autres : \(84\).

2. On choisit les quatre éléments parmi les neuf qui ne sont pas \(A\) : \(126\).

3. On choisit lequel de \(A,B\) est présent, puis \(3\) éléments parmi les \(8\) autres : \(2\binom{8}{3}=112\).

4. Par complément, on retire les parties ne contenant ni \(A\) ni \(B\) : \(\binom{10}{4}-\binom{8}{4}=210-70=140\).

1. On divise \(11!\) par les factorielles correspondant aux permutations des lettres identiques : \(\dfrac{11!}{4!\,4!\,2!}=34650\).

2. La lettre M est fixée ; on permute les dix lettres restantes avec les mêmes répétitions : \(3150\).

3. On fixe M au début et un I à la fin. Il reste \(3\) I, \(4\) S et \(2\) P à répartir sur \(9\) positions : \(\dfrac{9!}{3!\,4!\,2!}=1260\).

4. On regroupe les quatre I en un bloc. On permute alors \(8\) objets : le bloc I, M, quatre S et deux P. On divise par \(4!\) et \(2!\) : \(\dfrac{8!}{4!\,2!}=840\).

1. Il suffit de choisir les \(4\) membres de l'équipe \(X\); les autres forment automatiquement \(Y\). Donc \(70\) répartitions.

2. Dans \(\binom{8}{4}\), chaque partition non nommée est comptée deux fois : une fois par chacun des deux groupes de quatre. On divise donc par \(2\).

3. On choisit lequel de \(A,B\) va dans \(X\) : \(2\) choix, puis \(3\) autres membres de \(X\) parmi les \(6\) personnes restantes. Ainsi \(2\binom{6}{3}=40\).

4. La condition 'A et B séparés' est symétrique par échange des équipes. Chaque partition non nommée correspond à deux répartitions nommées, donc \(\dfrac{40}{2}=20\).

1. Chaque exécution correspond à un choix de deux indices distincts avec l'ordre canonique \(i\lt j\). Chaque paire non ordonnée est donc comptée exactement une fois.

2. Le programme compte les paires parmi six indices \(0,1,\ldots,5\), soit \(\binom{6}{2}=15\).

3. Les triplets vérifient \(i\lt j\lt k\). Ils correspondent exactement aux sous-ensembles à trois éléments de six indices : \(\binom{6}{3}=20\).

4. Une chaîne d'indices \(i_1\lt i_2\lt i_3\lt i_4\) choisit exactement quatre indices parmi huit, une seule fois. Le nombre d'itérations est \(\binom{8}{4}=70\).

1. Chaque position possède \(4\) choix indépendants, donc \(4^6=4096\).

2. La première lettre a \(4\) choix. Chacune des cinq suivantes doit être différente de la précédente, donc a \(3\) choix. Produit : \(4\times3^5=972\).

3. La première lettre est fixée à A. Les cinq positions suivantes ont chacune \(3\) choix, donc \(3^5=243\).

4. Les deux premières lettres sont fixées et respectent la contrainte. Chacune des quatre positions suivantes a \(3\) choix : \(3^4=81\).

1. On choisit \(3\) positions de \(1\) dans le premier bloc de six, puis \(2\) dans le second bloc : \(20\times15=300\).

2. Le premier \(1\) est fixé. Dans les cinq autres positions du premier bloc, on choisit encore \(2\) chiffres \(1\). Le dernier caractère est \(0\), donc les \(2\) chiffres \(1\) du second bloc sont choisis parmi les cinq positions restantes : \(10\times10=100\).

3. Dans le premier bloc, le premier caractère est \(0\), donc on choisit les \(3\) chiffres \(1\) parmi les cinq autres positions. Dans le second bloc, le dernier caractère fournit déjà un \(1\), donc il reste un seul \(1\) à placer parmi cinq positions : \(10\times5=50\).

4. Les deux cas possibles sont disjoints : commencer par \(1\) et finir par \(0\), ou commencer par \(0\) et finir par \(1\). On additionne : \(100+50=150\).

1. On forme deux blocs. Avec les six autres livres, cela donne \(8\) objets à permuter : \(8!\). Chaque bloc a \(2\) ordres internes, donc \(2\times2\times8!=161280\).

2. Soit \(E\) : A,B adjacents et \(F\) : C,D adjacents. On a \(|E|=|F|=2\times9!\) et \(|E\cap F|=4\times8!\). Donc \(|E\cup F|=4\times9!-4\times8!=1290240\).

3. On prend le complémentaire de \(E\cup F\) dans les \(10!\) permutations : \(3628800-1290240=2338560\).

4. Dans \(E\cup F\), les rangements où les deux paires sont adjacentes sont comptés comme 'au moins une' mais ne conviennent pas à 'exactement une'. On retire \(|E\cap F|=161280\) : \(1290240-161280=1128960\).

1. Il suffit de choisir les \(5\) positions des pas \(H\) parmi les \(12\) positions : \(\binom{12}{5}=792\).

2. On fixe deux pas \(R\), il reste \(10\) positions contenant \(5R\) et \(5H\). On choisit les cinq positions de \(H\) : \(\binom{10}{5}=252\).

3. On fixe deux pas \(H\), il reste \(10\) positions contenant \(7R\) et \(3H\). On choisit les trois positions de \(H\) : \(\binom{10}{3}=120\).

4. Les chemins se répartissent en deux classes : mêmes types aux extrémités ou types différents. Le cas 'mêmes types' compte \(252+120=372\). Le complément vaut \(792-372=420\).

1. On choisit successivement le premier, le deuxième puis le troisième parmi des athlètes distincts : \(8\times7\times6=336\).

2. On choisit la position de l'athlète A sur le podium : \(3\) choix, puis l'athlète A : \(3\) choix, puis un couple ordonné de deux athlètes B : \(5\times4\). Total \(180\).

3. On choisit les deux positions réservées au club A : \(\binom{3}{2}=3\). On ordonne deux athlètes distincts du club A : \(3\times2=6\). On choisit l'athlète B : \(5\) choix. Total \(90\).

4. On retire les podiums composés uniquement d'athlètes du club B : \(5\times4\times3=60\). Donc \(336-60=276\).

1. Les huit tâches distinctes peuvent être permutées de \(8!=40320\) façons.

2. L'échange de \(A\) et \(B\) met en bijection les ordres satisfaisant \(A\lt B\) et ceux satisfaisant \(B\lt A\). La moitié des permutations convient.

3. Dans chaque permutation des huit tâches, les trois tâches \(A,B,C\) apparaissent selon l'un des \(3!\) ordres relatifs, tous équiprobables par symétrie combinatoire. Un seul ordre relatif convient, donc \(\dfrac{8!}{3!}=6720\).

4. La contrainte sur \(A,B,C\) fixe un ordre relatif parmi \(3!\), et celle sur \(D,E\) un ordre parmi \(2\). Ces contraintes portent sur des ensembles disjoints de tâches. On obtient \(\dfrac{8!}{3!\,2}=3360\).

1. Pour chaque cardinal \(k\), il y a \(\binom{n}{k}\) choix pour \(A\), puis \(k\) choix pour l'élément marqué \(x\in A\). On obtient \(k\binom{n}{k}\), puis on additionne sur tous les \(k\).

2. On choisit \(x\) de \(n\) façons. Une fois \(x\) imposé dans \(A\), chacun des \(n-1\) autres éléments est libre d'appartenir ou non à \(A\), soit \(2^{n-1}\) choix. Total : \(n\times2^{n-1}\).

3. Les deux expressions comptent exactement le même ensemble d'objets marqués. Elles sont donc égales.

4. En appliquant l'identité avec \(n=8\), on obtient \(8\times2^7=8\times128=1024\).

1. La réunion contient \(p+q\) personnes et l'ordre ne compte pas. On choisit donc \(r\) personnes parmi \(p+q\) : \(\binom{p+q}{r}\).

2. On choisit indépendamment \(k\) personnes dans le premier groupe et \(r-k\) dans le second : produit des deux combinaisons.

3. Les comités sont partitionnés selon le nombre \(k\) de membres issus du premier groupe. La somme des nombres de comités de chaque classe doit donc être égale au nombre total \(\binom{p+q}{r}\).

4. La somme vaut \(\binom{5}{0}\binom{7}{4}+\binom{5}{1}\binom{7}{3}+\binom{5}{2}\binom{7}{2}+\binom{5}{3}\binom{7}{1}+\binom{5}{4}\binom{7}{0}=35+175+210+70+5=495\), égale à \(\binom{12}{4}\).

1. Un segment est déterminé par une paire non ordonnée de sommets : \(\binom{15}{2}=105\).

2. Parmi les \(105\) segments joignant deux sommets, \(15\) sont les côtés du polygone. Les autres sont des diagonales : \(105-15=90\).

3. Dans un polygone convexe, trois sommets distincts déterminent un triangle. Il y en a \(\binom{15}{3}=455\).

4. Quatre sommets distincts d'un polygone convexe déterminent un quadrilatère convexe. Le nombre est \(\binom{15}{4}=1365\).

1. Une main est une partie à cinq éléments du jeu de \(52\) cartes : \(\binom{52}{5}=2598960\).

2. On choisit \(2\) as parmi \(4\), puis \(3\) cartes non as parmi les \(48\) restantes : \(6\times17296=103776\).

3. On choisit la valeur du brelan : \(13\) choix, puis ses \(3\) couleurs : \(\binom{4}{3}=4\). On choisit ensuite une autre valeur pour la paire : \(12\) choix, puis ses \(2\) couleurs : \(\binom{4}{2}=6\). Produit : \(3744\).

4. On choisit la valeur du carré : \(13\) choix. Les quatre cartes de cette valeur sont alors imposées. La cinquième carte peut être n'importe laquelle des \(48\) autres cartes : \(13\times48=624\).