Exercices corrigés - Dénombrements (pratiques)

1. Pour le premier, on a $20$ choix possibles, pour le second $19,$ pour le troisième $18.$ Le nombre de podiums possibles est donc égal à $20\times 19\times 18=6840$.
2. Le premier concurrent est Emile. Pour les autres places, il y a $19$ puis $18$ choix possibles; Le nombre de podiums ainsi constitués est de $19\times 18$.
3. Il y a trois choix possibles pour la place d'Emile. Une fois ce choix fixé, il y a $19$ choix possibles pour la première des deux autres places, puis $18$ choix possibles pour la seconde des deux autres places. Le nombre de podiums vérifiant ces conditions est donc de $3\times 19\times 18$. On peut aussi compter le nombre total de podiums (qui vaut $20\times 19\times 18$) et lui soustraire le nombre de podiums sans Émile (qui vaut $19\times 18\times 17$). Le nombre de podiums avec Émile est alors $$20\times 19\times 18-19\times 18\times 17=(20-17)\times 19\times 18=3\times 19\times 18.$$ On retrouve (heureusement !) le même résultat.
4. L'ordre n'est plus important, et on cherche le nombre de choix de $3$ concurrents parmi $20$, c'est-à-dire $\binom {20}3=1140$.

1. Pour chaque boulangerie, il y a 7 choix possibles. Il y a donc $7^4$ façons d'attribuer un jour de fermeture hebdomadaire à chaque boulangerie.
2. On peut procéder comme suit pour dénombrer le nombre de possibilités. La première boulangerie peut fermer n'importe quel jour de la semaine, ce qui lui laisse 7 choix. La seconde boulangerie peut fermer n'importe quel autre jour : 6 choix. La troisième ne peut pas fermer l'un des jours déjà choisi, ce qui lui laisse 5 choix, et pour la dernière, il ne reste que 4 choix. Le nombre de possibilités est donc $7\times 6\times 5\times 4$.
3. On va raisonner par différence, et compter plutôt le nombre de possibilités pour que toutes les boulangeries ferment le même jour : il y a $7$ choix (on choisit juste le jour de fermeture commun). Le nombre de possibilités pour qu'il y ait au moins une boulangerie ouverte chaque jour est donc $7^4-7$.

1. 1. Il y a $9^3=9\times 9\times 9=729$ codes possibles.
   2. Pour chacun des deux premiers chiffres, il y a 9 choix possibles. Pour le dernier, il y a $4$ choix possibles (on peut choisir 2,4,6,8). Il y a donc $9\times 9\times 4$ tels codes.
   3. On va compter par différence. Il y a $8\times 8\times 8$ codes ne contenant pas du tout le chiffre 4. Il y a donc $9\times 9\times 9-8\times 8\times 8=217$ codes comprenant au moins une fois le chiffre 4.
   4. Il y a 3 choix pour la place dans le nombre où se situe le chiffre 4. Pour chacun des deux autres chiffres, il y a 8 choix possibles. Il y a donc $3\times 8\times 8$ tels codes.
2. 1. On cherche cette fois un arrangement de 3 chiffres parmi 9. Il y a donc $9\times 8\times 7$ choix possibles.
   2. Il y a cinq choix pour le dernier chiffre. Celui-ci choisi, il reste huit choix pour le premier chiffre, puis sept pour le deuxième. Il y a donc $8\times 7\times 5$ tels codes.
   3. Il y a 3 choix pour la place dans le nombre où on place le chiffre 6. Pour les autres chiffres, il y a d'abord 8 choix, puis 7 choix possibles (rappelons que tous les chiffres sont distincts). Le nombre de tels codes est donc de $8\times 7\times 3$.

• on choisit 2 hôtesses parmi 8 et un pilote parmi 4 pour le premier hélicoptère. Il y a donc $\binom 82\times 4=28\times 4=112$ tels choix.
• pour le deuxième hélicoptère, on choisit 2 hôtesses parmi les 6 restantes, puis un pilote parmi les 3 restants. Il y a donc $\binom 62\times 3=15\times 3=45$ tels choix.
• pour le troisième hélicoptère, on choisit 2 hôtesses parmi les 4 restantes, puis un pilote parmi les 2 restants. Il y a donc $\binom 42\times 2=6\times 2=12$ tels choix.
• pour le dernier hélicoptère, on n'a plus de choix à faire : on lui affecte les deux dernières hôtesses et le dernier pilote.

1. Il s'agit de choisir trois joueurs parmi 8. Le nombre de comités possibles est donc de $\binom 83=56$.
2. Il s'agit de choisir deux garçons parmi 6, puis une fille parmi 2. Le nombre de choix possibles est donc de $\binom 62\times\binom 21$.
3. On compte le nombre de comités comprenant 3 garçons : il vaut $\binom 63$ (il faut choisir trois garçons parmi 6). On a déjà compté le nombre de comités comprenant exactement deux garçons. Donc le nombre de comités comprenant au moins deux garçons vaut $\binom 62\times\binom 21+\binom 63$.
4. Il ne reste qu'à choisir le dernier membre du comité : il y a 6 comités comprenant à la fois Fred et Émile.
5. Voici deux méthodes possibles :
   • On compte les comités comprenant Fred, mais pas Émile, et les comités comprenant Émile, mais pas Fred. Dans le premier cas, on trouve $\binom 62$ comités (il reste à choisir deux joueurs parmi 6, puisqu'on ne peut plus prendre ni Fred, ni Émile). Dans le second cas, on a aussi $\binom 62$ comités. On compte enfin les comités ne comprenant ni Fred, ni Émile. Il y en a $\binom 63$. Finalement, le nombre total de comités ne comprenant pas simultanément Émile et Fred est $\binom 62+\binom 62+\binom 63=50$.
   • Plus simplement, on peut aussi soustraire du nombre total de comités ($56$, cf question 1) le nombre de comités comprenant à la fois Fred et Émile ($6$, cf question 4), et on retrouve bien $50$ comités ne comprenant pas simultanément Fred et Émile.

1. Il y a $\binom 82=28$ choix possibles (il s'agit de choisir deux éléments parmi 8).
2. Il y a $\binom 41$ choix possibles pour une botte gauche et $\binom 41$ choix possibles pour une botte droite. Le nombre total de choix formant une paire est donc $\binom 41\times\binom 41=16$.
3. Il y a de nombreuses façons de répondre à cette question mais la plus simple est de raisonner par différence. Il y a en effet $4$ choix pour que le deux bottes choisies appartiennent à la même personne. Comme il y a d'après la première question $28$ choix possible de deux bottes, il y a $28-4=24$ choix possibles de sorte que les deux bottes appartiennent à deux personnes différentes.

1. Les chaussures étant discernables, j'ai choisi $2$ chaussures parmi les $20$ de mon armoire. Il y a donc $\binom{20}2=190$ choix possibles.
2. Notons $E$ les tirages qui m'amènent à des chaussures de même couleur, et $E_N$, $E_M$, $E_B$ les tirages qui m'amènent à deux chaussures noires (resp. marron, resp. blanches). Alors $E=E_N\cup E_M\cup E_B$ et cette réunion est disjointe. On a donc $$\textrm{card}(E)=\textrm{card}(E_N)+\textrm{card}(E_M)+\textrm{card}(E_B).$$ Or, $\textrm{card}(E_N)=\binom{10}2$, puisque je peux choisir 2 chaussures parmi 10. Finalement, $$\textrm{card}(E)=\binom{10}2+\binom{6}2+\binom 42=66.$$
3. Il y a 10 choix possibles pour la chaussure droite. Une fois ce choix réalisé, il y a 10 choix possibles pour la chaussure gauche. Au total, il y a $10\times 10=100$ choix possibles.
4. Notons $A$ les tirages qui amènent une chaussure droite et une chaussure gauche de la même couleur. Comme précédemment, on va décomposer $A$ en $A_N\cup A_M\cup A_B$, où $A_N$ est l'ensemble des tirages amenant une chaussure droite noire et une chaussure gauche noire. On a $\textrm{card}(A_N)=5^2$ ($5$ choix pour la chaussure droite, $5$ choix pour la chaussure gauche) et finalement $$\textrm{card}(A)=5^2+3^2+2^2=38.$$
5. On compte d'abord le nombre de choix de deux chaussures qui amènent la même paire : il y en a $10$ (autant que de paires de chaussures). Par différence, le nombre de choix qui amènent à deux chaussures qui ne sont pas de la même paire est $\binom{20}2-10=180$.

1. Pour écrire un élément de $A$, on a
   • 8 choix pour le premier chiffre (tous sauf 0 et 1).
   • 9 choix pour les 6 autres chiffres (tous sauf 1).
   On a donc $\card(A)=8\times 9^6$.
2. Pour écrire un élément de $A_1$, on a
   • 8 choix pour le premier chiffre (tous sauf 0 et 1)
   • Notant $E$ l'ensemble des chiffres différents de 1 et du premier chiffre choisi, le reste de l'écriture de cet élément consiste en un choix ordonnée de 6 éléments distincts de $E$.
   Puisque $E$ comporte 8 élément, on a donc : $$\card(A_1)=8\times A_8^6=8\frac{8!}{2!}.$$
3. Un élément de $A$ est pair si son chiffre des unités est 0,2,4,6 ou 8. Il y a 5 façons de choisir ce chiffre des unités, 8 façons de choisir le premier chiffre, et $9^5$ autres de choisir les autres chiffres. On a donc : $$\card(A_2)=5\times 8\times 9^5.$$
4. Remarquons qu'un élément de $A_3$ ne comporte pas le chiffre zéro. Il y a $\binom{8}{7}$ façons de choisir 7 chiffres tous distincts parmi $\{2,3,\dots,9\}$, et une seule façon, ces 7 chiffres choisis, de les écrire en ordre croissant. On a donc $$\card(A_3)=\binom{8}{7}=8.$$

1. Une anagramme de CLERMONT consiste en une permutation des $8$ lettres de ce mot. Remarquons que toute permutation donnera un mot différent car toutes les lettres sont différentes. Le nombre d'anagrammes de CLERMONT est donc $8!$.
2. Cette fois, la première lettre doit être un C, et toute permutation des $7$ autres lettres donnera une anagramme différente. On a dont $7!$ telles anagrammes.
3. Il faut commencer par choisir la première lettre. On choisit une des $6$ consonnes. Ensuite, cette lettre étant fixée, toute permutation des $7$ autres lettres donnera une anagramme différente. Il y a donc $6\times 7!$ telles anagrammes.

• MATHS : 5!
• RIRE : 4!/2!
• ANANAS : 6!/(2!3!)

• choisir la position des 3 lettres $A$ : il y a $\binom 63$ choix possibles;
• choisir la position des 2 lettres $N$ : il y a $\binom 32$ choix possibles (il reste 3 places une fois qu'on a placé les $A$);
• le $S$ est alors placé.

1. Un trajet correspond à une suite de $10$ déplacements, dont $6$ vers la droite et $4$ vers le haut. Choisir un trajet correspond donc à écrire un mot de $10$ lettres comprenant $6$ fois la lettre $D$ et $4$ fois la lettre $H$. Le trajet est complètement déterminé par l'emplacement des $4$ lettres $H$ dans ce mot de $10$ lettres. Il y a donc $\binom {10}4$ chemins différents pour aller de $A$ à $B$. Remarquons qu'on aurait pu compter aussi les emplacements possibles pour la lettre $D$, on aurait trouvé $\binom{10}6$ ce qui est le même résultat !
2. Sur le même modèle, il y a $\binom{4}2$ chemins de $A$ à $C$ et $\binom62$ chemins de $C$ à $B$. Au trouve donc au total $\binom 42\times\binom62=90$ chemins de $A$ à $B$ en passant par $C.$

1. On choisit d'abord $2$ joueurs parmi les $2n$ joueurs pour le match 1, puis $2$ joueurs parmi les $2n-2$ joueurs restants pour le match 2, et ainsi de suite. Le nombre de façons d'organiser le premier tour, en tenant compte de l'ordre des matchs, est donc $$\binom{2n}2\times\binom{2n-2}2\times\cdots\times\binom{2}2=\frac{(2n)!}{2^n}.$$
2. Si l'ordre des matchs n'est plus pris en compte, alors il faut diviser en plus par le nombre de permutations possibles des matchs, c'est-à-dire $n!$. Le nombre de façons d'organiser le premier tour, sans tenir compte de l'ordre des matchs, est donc $\frac{(2n)!}{2^n\cdot n!}.$

1. 1. On est dans un cas où l’ordre et la répétition interviennent puisque les jetons sont tirés successivement et avec remise. A chaque tirage, on a $13$ choix possibles, et donc on obtient $13^6$ résultats possibles (on a dénombré des listes).
   2. 1. Pour obtenir exactement un jeton noir, on doit choisir à quel tirage on va tirer le jeton noir (6 choix possibles). Ensuite pour chaque choix de numéro de tirage, on a 8 choix possibles de jetons noirs et pour les 5 autres tirages, on a 5 possibilités à chaque fois puisqu'il y a 5 jetons blancs. Ainsi, on obtient : $6 \times 8 \times 5^5$ résultats possibles.
      2. On va dénombrer l’ensemble complémentaire. En effet, il y a exactement $5^6$ tirages sans jeton noir (à chaque fois, on a tiré un jeton blanc). Il y a donc $13^6-5^6$ tirages avec au moins un jeton noir.
      3. On a déjà dénombré les tirages avec exactement un jeton noir et les tirages sans jeton noir. L'ensemble recherché étant l'union disjointe des ensembles précédents, il y a $6 \times 8 \times 5^5+5^6$ tirages amenant au plus un jeton noir.
      4. Si on a deux fois plus de jetons noirs que de jetons blancs, c'est qu'on a tiré 4 jetons noirs et 2 jetons blancs. On commence par fixer les 2 tirages parmi 6 pour lesquels on a trouvé un jeton blanc : il y en a $\binom 62$. Ce choix fixé, il y a $5^2$ choix pour les jetons blancs et $8^4$ choix possibles pour les jetons noirs. On obtient au final $\binom 62\times 5^2\times 8^4$ tirages amenant 2 fois plus de jetons noirs que de jetons blancs.
2. 1. Si on tire les jetons successivement et sans remise, l'ordre intervient mais il n'y a plus de répétition. On dénombre des arrangements et il y a $13\times 12\times 11\times 10\times 9\times 8=13!/7!$ tirages possibles.
   2. 1. Pour obtenir exactement un jeton noir, on doit choisir à quel tirage on va tirer le jeton noir (6 choix possibles). Ensuite pour chaque choix de numéro de tirage, on a 8 choix possibles de jetons noirs et pour les 5 autres tirages, on doit choisir 5 jetons parmi 5 sans remise mais avec ordre : $5 \times 4 \times 3 \times 2 \times 1 = 5!$. Ainsi, on obtient $6 \times 8 \times 5!$ résultats possibles.
      2. On remarque qu'il n'y a aucun tirage sans jeton noir, puisque l'on fait 6 tirages, sans remise, et qu'il n'y a que 5 jetons blancs. Le nombre de tirages avec au moins un jeton noir est égal au nombre total de tirages, soit $13!/7!$.
      3. Comme il n'y a aucun tirage sans jeton noir, le nombre de tirages avec au plus un jeton noir est égal au nombre de tirages avec exactement un jeton noir, soit $6 \times 8 \times 5!$ résultats possibles.
      4. Comme précédemment, on tire 2 jetons blancs et 4 jetons noirs. On commence par fixer la place des 2 jetons blancs parmi les 6 tirages, il y a $\binom 6 2$ choix. Puis il y a $5\times 4$ choix pour les jetons blancs et $8\times 7\times 6\times 5$ choix possibles pour les jetons noirs. Finalement, on obtient $\binom 62\times 5\times 4\times 8\times 7\times 6\times 5$ choix possibles.
3. 1. On est dans le cas où ni l'ordre ni la répétition n'interviennent, on dénombre donc des combinaisons. Il y a donc $\binom{13}6$ résultats possibles.
   2. 1. On tire forcément tous les jetons blancs et un jeton noir parmi les 8 : il y a donc 8 tirages possibles.
      2. On remarque qu'il n'y a aucun tirage sans jeton noir, puisque l'on fait 6 tirages, sans remise, et qu'il n'y a que 5 jetons blancs. Le nombre de tirages avec au moins un jeton noir est égal au nombre total de tirages, soit $\binom{13}6$.
      3. Comme il n'y a aucun tirage sans jeton noir, le nombre de tirages avec au plus un jeton noir est égal au nombre de tirages avec exactement un jeton noir, soit $8$ résultats possibles.
      4. On doit tirer 2 jetons blancs parmi 5 et 4 jetons noirs parmi 8. Le nombre de tirages recherché est donc $\binom 52\times \binom 84$.

1. Il y a $\binom{52}{13}$ choix possibles pour le premier joueur, puis $\binom{52-13}{13}=\binom{39}{13}$ choix possibles pour le deuxième joueur, et encore $\binom{39-13}{13}=\binom{26}{13}$ pour le troisième. Le dernier joueur prend les 13 cartes restantes. Au total on trouve $$\binom{52}{13}\times\binom{39}{13}\times\binom{26}{13}=\frac{52!}{39!13!}\times\frac{39!}{26!13!}\times \frac{26!}{13!\times 13!}=\frac{52!}{(13!)^4}.$$
2. On choisit une couleur parmi 4 pour le premier joueur, puis une couleur parmi 3 pour le deuxième et enfin une couleur parmi 2 pour le troisième. Cela fait $4!$ possibilités. On peut aussi argumenter à l'aide du nombre de permutation de 4 couleurs.
3. On commence par choisir les deux joueurs qui ont chacun une couleur complète. Il y a $\binom 42$ tels choix. On choisit ensuite une couleur parmi $4$ pour le premier joueur, et une couleur parmi $3$ pour le deuxième joueur. Il reste pour le 3ème joueur à choisir $13$ cartes parmi les $26$ restantes tandis que le quatrième prend le reste. Mais il faut, parmi les choix de $13$ cartes parmi $26$, éliminer les deux configurations où les $13$ cartes sont de la même couleur (les deux couleurs restantes). On trouve donc : $$ \frac{4\times 3}{2}\times 4\times 3\times\left(\binom{26}{13}-2\right)=72\times\left( \binom{26}{13}-2\right).$$
4. Le dénombrement à réaliser est très similaire, mais il y a moins de choix pour choisir les deux joueurs qui ont la même couleur puisqu'on ne choisit plus deux joueurs quelconques, mais deux partenaires. Il n'y a donc que $2$ choix au lieu de $\binom 42$. Finalement, on trouve $\displaystyle 24\times\left( \binom{26}{13}-2\right).$

1. Il y a 4 choix pour la couleur. La couleur choisie, il suffit de choisir la plus haute carte de la main : il s'agit de n'importe quelle carte entre le 5 et l'as. Il y a donc 10 choix choix possibles pour la hauteur de la plus haute carte, et donc $4\times 10=40$ mains conduisant à une quinte flush.
2. Il y a 13 choix possibles pour la hauteur de la carte constituant le carré (carré d'as, carré de rois,...). Cette hauteur fixée, il faut encore choisir une carte parmi les 48 autres pour compléter la main. Il y a donc $13\times 48=624$ mains contenant un carré.
3. On choisit d'abord la hauteur des 3 cartes de même valeur. Il y a 13 choix. On choisit alors ces 3 cartes de même valeur. Il y a $\binom 43=4$ choix possibles. On choisit ensuite la hauteur des deux autres cartes. Il reste 12 choix. Puis on choisit ces 2 cartes de même valeur. Il y a $\binom 42=6$ choix. Finalement, le nombre de mains constituant un full est $$13\times 4\times 12\times 6=3744.$$
4. On va dénombrer d'abord le nombre de mains constituée de 5 cartes consécutives, qu'elles soient ou non de la même couleur. On retirera ensuite le nombres de quintes flush pour obtenir le nombres de mains constituées de 5 cartes qui ne sont pas toutes de la même couleur. Si on compte le nombre de mains constituées de 5 cartes consécutives, qu'elles soient ou non de la même couleur, alors on doit choisir la hauteur de la carte la plus haute. Comme précédemment, il y a 10 choix possibles. Ensuite, pour chacune des cinq hauteurs consécutives, on choisit l'une des 4 couleurs, ce qui fait $4^5$ choix. Finalement, le nombre de mains correspondant est $10\times 4^5=10240$ ce qui fait que le nombre de quintes est exactement $10240-40=10200$.
5. On compte le nombre de mains comprenant 3 cartes de même niveau et qui ne contient pas un carré : il y a 13 choix pour le niveau, $\binom 43=4$ choix de 3 couleurs parmi 4 pour ce niveau. Puis, pour les deux autres cartes, il faut choisir deux cartes parmi 48 (on doit exclure la dernière carte de même hauteur, sinon on aurait un carré), soit $\binom {48} 2=48\times 47/2=1128$ choix. Il y a donc $13\times 4\times 1128=58656$ mains contenant 3 cartes de même niveau, mais pas de carrés. Pour dénombrer le nombre de brelans, il faut retirer les fulls. Il y a donc $58656-3744=54912$ brelans.
   Attention au raisonnement faux suivant : on pourrait compter le nombre de mains comprenant 3 cartes de même niveau : il y a 13 choix pour le niveau, $\binom 43=4$ choix de 3 couleurs parmi 4 pour ce niveau. Puis, pour les deux autres cartes, il faut choisir deux cartes parmi 52-3=49, soit $\binom {49} 2=49\times 48/2=1176$ choix. Il y a donc $13\times 4\times 1176=61152$ mains contenant 3 cartes de même niveau. Pour dénombrer le nombre de brelans, il faut retirer les carrés et les fulls. Il y a donc $61152-624-3744=56784$ brelans. Ce raisonnement est faux car quand on a compté le nombre de mains contenant 3 cartes de même niveau, on a compté 4 fois chaque carré. En effet, un carré d'as peut apparaitre en choisissant d'abord as de coeur, de carreau, de trèfle, puis en complétant avec as de pique, ou en choisissant as de coeur, de carreau, de pique, puis en complétant avec as de trèfle, etc... Si on veut réaliser un dénombrement correct avec cette méthode, il faut retirer quatre fois le nombre de carrés, et on a bien $61152-4\times 624-3744=54912$.

1. Il n'y a pas d'ordre et pas de répétition sur les cartes : un tirage est donc une combinaison de 5 cartes parmi 32. Il y a : $\binom{32}5=201376$ tirages différents.
2. Pour obtenir 5 carreaux, il faut choisir 5 cartes parmi 8 : il y a $\binom85$ tels tirages. De même pour obtenir 5 piques. Comme les deux cas sont disjoints, il y a $2\times \binom85=112$ tels tirages différents.
3. Il y a $\binom82$ façons de choisir 2 carreaux parmi 8 puis, pour chacune de ces façons, il y a $\binom83$ façons de choisir 3 piques. Le nombre de tirages recherché est donc : $\binom82\times \binom83=1568$.
4. On compte le complémentaire, c'est-à-dire les tirages sans rois : il faut alors choisir 5 cartes parmi 28, il y a $\binom{28}5$ tels tirages. Le nombre de tirages recherché est donc : $\binom{32}5-\binom{28}5=103096$.
5. On a déjà compté les tirages sans roi. Pour les tirages comprenant exactement un roi, il y a 4 façons de choisir le roi, puis, pour chacune de ces façons, $\binom{28}4$ façons de choisir les autres cartes. On en déduit qu'il y a $\binom{28}5+4\binom{28}{4}=180180$ tels tirages.
6. On sépare les tirages contenant le roi de pique et ceux ne contenant pas le roi de pique.
   • si le tirage ne contient pas le roi de pique, il y a $\binom32$ choix différents de 2 rois parmi 3, puis $\binom73$ choix de 3 piques parmi 7 (tous sauf le roi de pique).
   • si le tirage contient le roi de pique, il reste 3 choix pour le roi différent du roi de pique, puis $\binom{7}2$ choix pour les deux autres piques. Cela faisant, on n'a tiré que 4 cartes. Il reste une carte à choisir qui n'est ni un roi, ni un pique, et donc $32-(4+7)=21$ choix (attention à ne pas compter à nouveau deux fois le roi de pique!).
   Finalement, le nombre de tirages possibles est : $$\binom32\times \binom73+3\times \binom{7}2\times 21=1428.$$

1. Il y a $3!$ façons de choisir l'ordre des matières. Une telle façon choisie, il y a $4!$ façons de ranger les livres de mathématiques, $6!$ façons de ranger les livres de physique, et $3!$ façons de ranger les livres de chimie. Le nombre de rangements possible est donc : $3!4!6!3!$.
2. Il peut y avoir $0,1,\dots,9$ livres placés avant les livres de mathématiques. Il y a donc $10$ choix du nombre de livres placés avant le livre de mathématiques. Ce choix fait, il y a $4!$ façons d'ordonner les livres de mathématiques, et $9!$ façons d'ordonner les autres : il y a donc en tout $10\times 4!\cdot9!=10!\cdot 4!$ rangements différents.

1. Il faut d'abord choisir $n$ points parmi ces $p$ points. Il y a $\binom pn$ tels choix. Ces points $A_1,\dots,A_n$ étant choisis, on fixe un premier sommet comme origine. On choisit ensuite le sommet suivant pour lequel il y a $n-1$ choix, puis le troisième sommet, pour lequel il y a $n-2$ choix, etc... Il y a donc $(n-1)!$ possibilités pour ordonner les sommets. Mais attention, procédant ainsi, on compte chaque polygone deux fois car l'ordre global des points n'importe pas (par exemple, le polygone $ABCD$ est le même que le polygone $ADCB$). Finalement, on trouve qu'il y a $\frac 12(n-1)!\binom pn$ polygones possibles à $n$ sommets choisis parmi $p$ points du plan.
2. Une diagonale est définie par deux sommets non consécutifs. On choisit donc d'abord un premier sommet $A$ parmi les $n$ sommets du polygone. On choisit ensuite un deuxième sommet parmi les sommets du polygone qui ne sont ni $A$ ni un sommet adjacent à $A$. Il y a $n-3$ choix. Mais ce faisant, on compte deux fois chaque diagonale (la diagonale $(AB)$ est comptée en choisissant $A$, puis $B$, et en choisissant $B$, puis $A$). Le nombre de diagonales est donc $\frac{n(n-3)}2$.

1. Il y a deux listes possibles à 1 terme, et aucune ne comporte deux 1 consécutifs. Donc $u_1=2$. Il y a 4 listes à 2 termes, dont une seule comporte deux 1 consécutifs. Donc $u_2=3$.
2. Considérons une liste à $n$ termes n'ayant pas deux 1 consécutifs.
   • ou bien elle se termine par un 1. Le terme précédent est donc forcément un 0, et pour les $n-2$ premiers termes, la seule contrainte est qu'il n'y ait pas deux 1 consécutifs. Il y a donc $u_{n-2}$ telles listes.
   • ou bien elle se termine par un 0. Il n'y a pas de contraintes sur les $n-1$ premiers termes, si ce n'est qu'il ne faut pas qu'il y ait deux 1 consécutifs. Il y a donc $u_{n-1}$ telles listes.
   On a donc réalisé une partition des listes à $n$ termes ne comportant pas deux $1$ consécutifs, et $u_n=u_{n-1}+u_{n-2}$.

3. Variables :
    U entier
    V entier
    W entier
    N entier
   Traitement
     2->U
     3->V
     Pour N allant de 3 à 20 faire
       U+V->W
       V->U
       W->V
     Fin Pour
     Afficher V
   

4. On peut associer à chaque questionnaire une liste de 0 et de 1, le $i$-ème terme vaut 1 si la réponse est juste, et 0 si la réponse est fausse. L'énoncé nous dit que les 17712 listes obtenues ne comportent deux termes 1 consécutifs. Or, il y a $u_{20}=17711$ telles listes différentes. Deux des listes doivent donc être identiques, et il y a bien deux candidats qui ont répondu de la même manière aux questions.

• ou bien on descend une seule marche : dans ce cas, il reste un escalier à $n-1$ marches à descendre, et donc $S(n-1)$ possibilités;
• ou bien on descend deux marches : dans ce cas, il reste un escalier à $n-2$ marches à descendre, et donc $S(n-2)$ possibilités;
• ou bien on descend trois marches : dans ce cas, il reste un escalier à $n-3$ marches à descendre, et donc $S(n-3)$ possibilités.

def S(n):
      if n<1:
           return 0
      elif n==1:
           return 1
      elif n==2:
           return 2
      elif n==3:
           return 4
      else:
           return S(n-1)+S(n-2)+S(n-3)

• ou bien l'une des classes, disons $\overline{m_j}$, est égale à $\bar 0$. Dans ce cas, $m_j$ est divisible par $k$.
• ou bien aucune de ces classes n'est égale à $\bar 0$. Mais alors, $\overline{m_1},\dots,\overline{m_k}$ vit dans $\{\bar 1,\dots,\overline{k-1}\}$ et donc toutes les classes ne peuvent pas être différentes. Autrement dit, il existe $j<\ell$ tel que $\overline{m_j}=\overline{m_\ell}$, c'est-à-dire que $m_\ell-m_j$ est divisible par $k$. Ceci prouve le résultat dans ce cas puisque $m_\ell-m_j=n_{j+1}+\cdots+n_{\ell}$.

1. On a 36=4*9 choix pour placer le premier trou. On ne peut ensuite plus choisir ni ce carré, ni les 3 carrés obtenus à partir de celui-ci par rotation. Il reste donc 32=4*8 choix pour placer le second trou. On a ensuite 4*7 choix pour placer le troisième trou, et ainsi de suite... jusque 4 choix pour placer le 9ème trou. Mais attention! Ce faisant, on compte certaines grilles deux fois. En effet, on obtient la même grille si on échange le premier trou et le deuxième trou.... Il faut diviser donc le total obtenu par le nombre de permutations possibles entre les 9 trous, soit 9! Finalement, le nombre de grilles possibles est $$\frac{4\times 9\times 4\times 8\times 4\times 7\times\dots\times 4\times 1}{9!}=4^9.$$
2. Si on veut construire une grille de Fleissner, il faut pouvoir réaliser $n^2/4$ trous (pour qu'avec les 4 positions, on puisse obtenir $n^2$ trous). Ainsi, $n$ doit être pair (et dans ce cas, $n^2$ est bien un multiple de 4). Ensuite, on procède comme dans le cas précédent : on a $n^2=4\times\frac{n^2}{4}$ choix pour le premier carré, $n^2-4=4\times \left(\frac{n^2}4-1\right)$ choix pour le deuxième carré,... En n'oubliant pas de diviser par la factorielle de $\frac{n^2}4$, on obtient que le nombre de grilles est $4^{n^2/4}$.