\chapter{Combinatoire et dénombrements}


\section{Principes de base}

La \textit{combinatoire} est la partie des mathématiques qui permet d'étudier les diverses configurations de sous-ensembles d'éléments d'un ensemble fini.

\bigskip

Les \textit{dénombrements} permettent d'énumérer le nombre de configurations possibles de ces sous-ensembles.

\subsection{Cardinal d'un ensemble}

\begin{defin}
Le \textit{cardinal} d'un ensemble $A$ est le nombre d'éléments contenus dans~$A$. 

On le note:
\[
\card(A).
\]
\end{defin}

\begin{exemple}
Si $A$ désigne l'ensemble des cartes qui constituent un jeu de 32 cartes alors $\card(A) = 32$.
\end{exemple}

\begin{defin}
On dit qu'un ensemble $A$ est \textit{fini} si $\card(A)$ n'est pas infini.
\end{defin}

\subsection{Principe additif}

\begin{prop}
Soient $A$ et $B$ deux ensembles finis disjoints, c'est-à-dire n'ayant aucun élément commun, tels que $\card(A)=n$ et $\card(B)=m$. Alors, le nombre de façons de prendre un élément dans $A$ \underline{ou} un élément dans $B$ est égal à $n+m$.
\end{prop}

\begin{exemple}
Dans ma bibliothèque, il y a 20 romans et 10 bandes dessinées. 

Je peux donc y choisir un livre de $20 + 10 = 30$ façons différentes.
\end{exemple}

\subsection{Principe multiplicatif}

\begin{prop}
Soient $A$ et $B$ deux ensembles finis tels que $\card(A)=n$ et $\card(B) = m$.

Le nombre de façons de prendre un élément dans $A$ \underline{et} un élément dans $B$ est égal à $n \times m$.
\end{prop}

\begin{exemple}
Dans ma bibliothèque, il y a 20 romans et 10 bandes dessinées. 

Je souhaite prendre un livre de chaque sorte. Il y a donc $20 \times 10= 200$ possibilités.
\end{exemple}

\newpage

Les principe multiplicatif peut se représenter sous la forme d'un \textit{arbre des possibilités}:

\begin{center}
\begin{tikzpicture}
\fill[courbe2,opacity=0.1, rounded corners] (1.75,-2.5) rectangle (2.25,2.5);
\fill[courbe4,opacity=0.1, rounded corners] (3.75,3.5) rectangle (4.25,.5);
\fill[courbe4,opacity=0.1, rounded corners] (3.75,-3.5) rectangle (4.25,-.5);

\node[courbe] (b11) at (4,3) {$b_1$};
\node[courbe] at (4,2) {$\vdots$};
\node[courbe] (bm1) at (4,1) {$b_m$};

\node at (4,0) {$\vdots$};

\node[courbe] (b12) at (4,-1) {$b_1$};
\node[courbe] at (4,-2) {$\vdots$};
\node[courbe] (bm2) at (4,-3) {$b_m$};

\node[courbe] (a1) at (2,2) {$a_1$};
\node[courbe] at (2,0) {$\vdots$};
\node[courbe] (an) at (2,-2) {$a_n$};

\draw[courbe3, thick] (0,0) -- (a1.west);
\draw[courbe3, thick] (0,0) -- (an.west);
\draw[courbe3, thick] (a1.east) -- (b11.west);
\draw[courbe3, thick] (a1.east) -- (bm1.west);
\draw[courbe3, thick] (an.east) -- (b12.west);
\draw[courbe3, thick] (an.east) -- (bm2.west);

\draw [pen colour={courbe4}, thick, decorate,decoration = {calligraphic brace,amplitude=10pt,raise=3pt}] (4.5,3.5) --  (4.5,0.75);
\draw [pen colour={courbe4}, thick, decorate,decoration = {calligraphic brace,amplitude=10pt,raise=3pt}] (4.5,-.5) --  (4.5,-3.5);
\node[courbe4, right] at (5,2.1) {$m$ possibilités};
\node[courbe4, right] at (5,-1.9) {$m$ possibilités};

\draw [pen colour={courbe2}, thick, decorate,decoration = {calligraphic brace,amplitude=5pt,raise=3pt}] (2.5,-2.75) -- (1.5,-2.75);
\node[below,courbe2] at (2,-3) {$n$ possibilités};

\draw [pen colour={courbe}, thick, decorate,decoration = {calligraphic brace,amplitude=10pt,raise=3pt}] (8,3.5) --  (8,-3.5);
\node[right,courbe] at (8.5,0) {$n\times m$ possibilités};
\end{tikzpicture}
\end{center}

On peut aussi considérer un tableau  à $n$ colonnes et $m$ lignes : il comporte $n \times m$ cellules.

\section{Dénombrement}

\subsection{Factorielle}

\begin{defin}
La factorielle d'un nombre entier $n$ est le nombre :
\[
n! = 1 \times 2\times 3\times 4\times \cdots \times (n-1) \times n.
\]
\end{defin}

\begin{exemple} 
$5! = 1 \times 2\times 3\times 4\times 5 = 120$.
\end{exemple}

\subsection{Permutation}

\begin{defin}
Soit $E$ un ensemble à $n$ éléments, $n\in\N^*$.

Une \textit{permutation} de $E$ est un ensemble \textit{ordonné} (l'ordre compte) composé des $n$ éléments de $E$.
\end{defin}

\begin{exemple}
Si $E=\{1;2;3\}$ alors $F=\{2;3;1\}$ est une permutation de $E$.
\end{exemple}

\begin{rem}
$E$ est une permutation de $E$.
\end{rem}

\begin{prop}
Il y a $n!$ permutations d'un ensemble à $n$ éléments.
\end{prop}

\subsection{p-uplet (ou p-liste)}

\begin{defin}
Soient $n$ et $p$ deux entiers naturels non nuls tels que $p \leqslant n$, et soit $E$ un ensemble à $n$ éléments.

Un \textit{p-uplet} (ou une \textit{p-liste}) de $E$ est une liste \textit{ordonnée} de $p$ éléments pris parmi les $n$ éléments de $E$.
\end{defin}

\begin{exemple}
Un digicode à 4 chiffres est un 4-uplet de l'ensemble $\{0;1;2;3;4;5;6;7;8;9\}$. 

Le 4-uplet \{1;1;1;0\} est différent du 4-uplet \{0;1;1;1\}.
\end{exemple}

\begin{prop}
Le nombre de $p$-uplets pris dans un ensemble à $n$ éléments est égal à $n^p$.
\end{prop}

\begin{exemple}
Il y a $10^4=\numprint{10000}$ possibilités pour un digicode composé de 4 chiffres.
\end{exemple}

\subsection{Arrangement}

\begin{defin}
Soit $n$ un entier naturel non nul, et soit $E$ un ensemble à $n$ éléments.

Un \textit{arrangement} de $p$ éléments de $E$ est un $p$-uplet d'éléments \underline{distincts}. 
\end{defin}

\begin{exemple}
Le podium d'une course à 20 participants est un arrangement constitué du premier arrivé, puis du deuxième et enfin du troisième.
\end{exemple}

\begin{prop}
Le nombre d'arrangements de $p$ éléments pris dans un ensemble à $n$ éléments est:
\[
A_n^p = \dfrac{n!}{(n-p)!}=n(n-1)(n-2)\cdots(n-p+1).
\]
\end{prop}

\begin{exemple}
$A_{20}^3=20\times19\times18=\numprint{6840}$.\\[6pt]
Il y a donc \numprint{6840} podiums possibles pour une course à 20 participants.
\end{exemple}

\newpage

\subsection{Combinaison}

\begin{defin}
Soient $n$ et $p$  deux entiers naturels non nuls tels que $p \leqslant n$, et soit $E$ un ensemble à $n$ éléments.

Une \textit{combinaison} de $p$ éléments de $E$ est un ensemble \textit{non ordonné} à $p$ éléments \underline{distincts} pris parmi les $n$ éléments de $E$.
\end{defin}

\begin{exemple}
Sur un jeu de 32 cartes, une main de 5 cartes est une combinaison.
\end{exemple}

\begin{prop}
Le nombre de combinaisons de $p$ éléments d'un ensemble $E$ à $n$ éléments est égal à :
\[
\dbinom{n}{p}=\dfrac{A_n^p}{p!}=\dfrac{n!}{p!(n-p)!}=\dfrac{n(n-1)\cdots(n-p+1)}{p!}.
\]
\end{prop}

\begin{exemple}
$\dbinom{32}{5}=\dfrac{32\times31\times\cdots\times(32-5+1)}{5!}=\numprint{201376}$.

Il y a donc \numprint{201376} mains de 5 cartes possibles sur un jeu de 32 cartes.
\end{exemple}

\begin{prop}
Pour tous entiers naturel $n$ et $p$ tels que $p\leqslant n$ et $n\neq0$,
\[
\sum_{k=0}^n\dbinom{n}{k}=2^n.
\]
\end{prop}

\begin{prop}[relation de Pascal]
Pour tous entiers naturel $n$ et $p$ tels que $p\leqslant n$ et $n\neq0$,
\[
\dbinom{n}{p}=\dbinom{n-1}{p-1}+\dbinom{n-1}{p}.
\]
\end{prop}

De la propriété \ref{prop:relation de Pascal}, on déduit un tableau regroupant les différentes valeurs de $\dbinom{n}{p}$ suivant les valeurs de $n$ et $p$ : c'est le \textit{triangle de Pascal}.

\medskip

\begin{center}
\arrayrulecolor{chapterbacknum}
\begin{tikzpicture}
\node[inner sep = 0pt, outer sep = 0pt, fill = white] (tab) {
\begin{tabular}{|>{\columncolor{chapterbacknum}\color{white}\centering\arraybackslash}m{1cm}|*7{Sc|}}
\rowcolor{chapterbacknum}\hline
\diagbox[width=14mm,height=7mm]{$n$}{\raisebox{1mm}{$p$}} &\color{white} 0 &\color{white} 1 &\color{white} 2 &\color{white} 3  &\color{white}4 &\color{white} 5 &\color{white} 6\\
\hline
0 & 1 & & & & & & \\
\hline
1 & 1 & 1 & & & & & \\
\hline
2 & 1 & 2 & 1 & & & & \\
\hline
3 & 1 & \multicolumn{2}{c|}{\cellcolor{courbe!10}3 {\color{courbe3}$\xrightarrow{+}$} 3} & 1 & & & \\
\hline
4 & 1 & 4 &\cellcolor{courbe!10}  6
& 4 & 1 & & \\
\hline
5 & 1 & 5 & 10 & 10 & 5 & 1 & \\
\hline
6 & 1 & 6 & 15 & 20 & 15 & 6 & 1\\
\hline
\end{tabular}};
\drawshadow{tab}{black}
\node at ($(tab)+(-0.3,-0.7)$) {\rotatebox{-90}{\color{courbe3}$\xrightarrow{=}$}};
\end{tikzpicture}

\medskip

\textit{Début du triangle de Pascal}
\end{center}

\newpage

Pour construire et afficher un triangle de Pascal, on peut utiliser le programme Python suivant :

\begin{python}
def trianglePascal(n):
    T = [[0] * (n+1) for p in range(n+1)]
    for n in range(n+1):
        if n == 0:
            T[n][0] = 1
        else:
            for k in range(n+1):
                if k == 0:
                    T[n][0] = 1
                else:
                    T[n][k] = T[n-1][k-1] + T[n-1][k]
    return T


T = trianglePascal(15)

for i in range(len(T)):
    print(T[i][:i+1])
\end{python}

Pour résumer, on retiendra le tableau suivant :\enlargethispage*{2cm}

\begin{center}
\begin{tikzpicture}
\node[inner sep = 0pt, outer sep = 0pt, fill = white] (tab) {
\begin{tabular}{%
|>{\columncolor{chapterbacknum}\color{white}}S{m{37mm}}%
|>{\centering\arraybackslash}S{m{15mm}}%
|>{\centering\arraybackslash}S{m{2cm}}%
|>{\centering\arraybackslash}S{m{3.7cm}}
|>{\centering\arraybackslash}S{m{3cm}}|}
\rowcolor{chapterbacknum}\hline
~ &\color{white} \raisebox{2mm}{Ordre} &\color{white} \raisebox{2mm}{Modèle} &\color{white} \raisebox{2mm}{Exemples} & \color{white} \raisebox{2mm}{Formules}\\
 \hline
 Permutation & oui & tirage sans remise & anagramme & $n!$ \\
 \hline
 $p$-liste & oui & tirage avec remise  & digicode & $n^p$\\
 \hline
 Arrangement $A_n^p$ & oui & tirage sans remise &podium d'une course & $\dfrac{n!}{(n-p)!}$\\
 \hline
 Combinaison $\dbinom{n}{p}$  & \raisebox{-2mm}{non} & \raisebox{-2mm}{\begin{minipage}{20mm}\centering tirage sans remise\end{minipage}} & \raisebox{-2mm}{\begin{minipage}{37mm}\centering main dans un jeu de cartes\end{minipage}} & $\dfrac{n!}{p!(n-p)!}$\\
 \hline
\end{tabular}};
\drawshadow{tab}{black}
\end{tikzpicture}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotype
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exercicetype}{principes additifs et multiplicatifs}{}
Pour chacune des questions suivantes, indiquer le principe de dénombrement à utiliser et effectuer le calcul.
\begin{enumerate}
\item Le carte d'un restaurant propose 5 entrées différentes, 4 plats et 3 desserts.
\begin{enumerate}
\item Luc n'a pas le temps de faire un repas complet: il prend soit une entrée, soit un plat, soit un dessert.

Combien de choix a-t-il ?

\item Virginie a le temps de prendre une entrée, un plat et un dessert.

Combien de menus différents peut-elle composer ?
\end{enumerate}

\item Dans une classe de 35 élèves, 20 étudient l'allemand, 15 l'espagnol et 8 aucune de ces deux langues. 

Combien d'élèves étudient l'allemand et l'espagnol ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item
\begin{enumerate}
\item On utilise ici le principe additif: Luc choisit une entrée \underline{ou} un plat \underline{ou} un dessert. Il a donc:
\[
5 + 4 + 3 = 12 \text{ choix possibles.}
\]

\item Un menu est un produit cartésien des ensembles \{ entrées \}, \{ plats \} et \{ desserts \}. Il y a donc:
\[
5 \times 4 \times 3 = 60 \text{ menus possibles. }
\]
\end{enumerate}

\item L'ensemble de la classe est un ensemble $C$. 

Les élèves faisant allemand constituent un ensemble $A$.

Les élèves faisant espagnol constituent un ensemble $E$.

Les élèves ne faisant ni allemand ni espagnol constituent un ensemble $R$.

On a alors: $\begin{aligned}[t]
\card(C) & = \card(A) + \card(E) - \card( A \cap E )+ \card(R)\\
35		 & = 20 + 15 - \card(A \cap E) + 8\\
\Rightarrow \card(A \cap E) & = 35 - 35 + 8 = 8.
\end{aligned}$
\end{enumerate}
\end{exercicetype}

%%%

\vspace*{-2em}
\enlargethispage*{\baselineskip}
\begin{exercicetype}{reconnaître le modèle combinatoire}{}
\begin{enumerate}
\item Un code secret pour un coffre-fort est composé de 4 chiffres, chacun pouvant être de 0 à 9. 

Combien de codes différents peut-on créer ?

\item Cinq amis (Alice, Bob, Charles, David, Ève) veulent s'asseoir sur un banc de 5 places.

Combien de façons différentes peuvent-ils s'asseoir ?

\item Dans une course de 10 athlètes, seuls les 3 premiers seront récompensés. 

Combien de podiums différents peut-on obtenir ?

\item Un professeur doit choisir 3 élèves parmi 25 pour former un groupe de travail. 

Combien de groupes différents peut-il former ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le code secret est un $4$-uplet d'un ensemble à 10 éléments (10 chiffres). 

Il y a donc $10^4=\numprint{10000}$ codes possibles.

\item Il s'agit ici d'une permutation d'un ensemble à 5 éléments. Il y a donc $5!=120$ possibilités.

\item Il s'agit ici d'un arrangement de 3 éléments d'un ensemble à 10 éléments. 

Il y a donc $A_{10}^3 = 10\times9\times8=720$ podiums possibles.

\item L'ordre ne compte pas ici, donc il s'agit d'une combinaison de 3 éléments dans un ensemble à 25 éléments. 

Il y a donc $\dbinom{25}{3}=\numprint{2300}$ groupes possibles.
\end{enumerate}
\end{exercicetype}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercices
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\sectionnn{Principes additif et multiplicatif}

%%%

\begin{exocor}{l'imprimeur}[1]
Un imprimeur doit imprimer des calendriers pour une même société tous les ans. Afin de réduire ses coûts, il décide de créer tous les modèles possibles la même année.
\begin{enumerate}
\item Combien de pages différentes doit-il confectionner pour le mois de janvier ?
\item Combien de pages différentes doit-il confectionner pour le mois de février ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le mois de janvier peut commencer par \og Lundi \fg, \og Mardi \fg, ... ou \og Dimanche \fg, soit 7 possibilités. 

L'imprimeur doit donc imprimer 7 pages différentes pour le mois de janvier.

\item Le mois de février comporte 28 ou 29 jours; il y a donc deux types de pages à créer:
\begin{itemize}
\item pour les mois à 28 jours, il doit créer 7 pages différentes (car le mois peut commencer par 7 jours différents);
\item pour les mois à 29 jours, il doit aussi créer 7 pages différentes.
\end{itemize}

Finalement, il doit créer $7+7=14$ pages différentes.
\end{enumerate}
\end{exocor}


%%%

\begin{exocor}{au restaurant}[1]
Un restaurant propose à sa carte un menu où il faut choisir une entrée, un plat et un dessert.

Sont proposés trois entrées, six plats et 2 desserts.

Combien de repas différents peut-on constituer ?

\tcblower

Il y a 3 entrées possibles, 6 plats possibles et 2 desserts possibles, donc il y a $3\times6\times2=36$ repas différents.
\end{exocor}

%%%

\begin{exocor}{dans la bibliothèque}[1]
Dans la bibliothèque de Gaspard, il y a 20 polars, 7 livres sur l'art et 5 livres sur les routards.

Il souhaite ne prendre que deux livres de catégories différentes.

Combien de possibilités a-t-il ?

\tcblower

On utilise le principe multiplicatif pour chaque couple possible (où l'ordre ne compte pas).
\begin{itemize}
\item Il y a $20\times7=140$ possibilités pour les couples polars/art;
\item Il y a $20\times5=100$ possibilités pour les couples polars/routards;
\item Il y a $7\times5=35$ possibilités pour les couples art/routards.
\end{itemize}
Ensuite, on applique le principe additif : on a le choix entre les couples polars/art \textit{ou} polars/routards \textit{ou} art/routards, ce qui fait: $140+100+35\text{ possibilités}$.

\begin{attention}
Le mot \og OU \fg{} correspond à une addition;

Le mot \og ET \fg{} correspond à une multiplication.
\end{attention}
\end{exocor}

%%%

\begin{exocor}{coordonnées aléatoires}[1]
Voici un programme Python qui permet de choisir au hasard les coordonnées d'un point dans le plan muni d'un repère :

\begin{python}
from random import randint
x = randint(-10,10) # nombre entier aléatoire compris entre -10 et 10 inclus
y = randint(-10,10)
\end{python}

\medskip

Combien de coordonnées peut-on obtenir ?

\tcblower

Ce programme choisit au hasard un nombre entier entre $-10$ et 10 (inclus). Il y a donc 21 possibilités pour $x$ et pour $y$.

Le nombre total de possibilités est donc $21 \times 21 = 441$.
\end{exocor}

%%%

\begin{exocor}{nombres à 6 chiffres}[2]
\begin{enumerate}
\item Combien y a-t-il de nombres entiers à 6 chiffres ?
\item Combien de nombres entiers à 6 chiffres comportent des chiffres tous distincts ?
\item Combien existe-t-il de nombres entiers à 6 chiffres dont les chiffres consécutifs sont de parité différente ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item De \numprint{100000} à \numprint{999999}, il y a $9\times10^5=\numprint{900000}$ nombres.

Il y a en effet 9 possibilités (de 1 à 9) pour le premier chiffre, puis 10 possibilités (de 0 à 9) pour les 5 autres chiffres.

\item On souhaite que les 6 chiffres soient tous distincts.

Il y a 9 choix possibles pour le premier chiffres (de 1 à 9), puis 9 choix possibles pour le deuxième chiffre (de 0 à 9 sans le chiffre choisi en premier), puis 8 choix possibles pour le 3\ieme{} chiffre, etc.

D'après le principe multiplicatif, il y a donc $9\times9\times8\times7\times6\times5=\numprint{136080}$ nombres possibles.

\item 
\begin{itemize}
\item Si le premier chiffre est pair: on a le choix entre 2, 4, 6 ou 8, donc 4 possibilités.

Pour le deuxième chiffre, on a le choix entre 1, 3, 5, 7 ou 9, donc 5 possibilités.

Pour le troisième chiffre, on a le choix entre 0, 2, 4, 6 ou 8, soit 5 possibilités.

etc.

Il y a donc $4\times5^5=\numprint{12500}$ nombres possibles.


\item Si le premier chiffre est impair: on a le choix en 1, 3, 5, 7 et 9, donc 5 possibilités.

Pour les 5 autres chiffres, on a aussi le choix entre 5 chiffres.

Il y a donc $5^6=\numprint{15625}$ nombres possibles.
\end{itemize}
Ainsi, en tout, il y a $\numprint{12500}+\numprint{15626}=\numprint{28125}$ nombres possibles.
\end{enumerate}
\end{exocor}


\newpage

\sectionnn{Arrangements, permutations, combinaisons et p-uplets}

%%%

\begin{exocor}{QCM}[1]
Dans chacune des questions suivantes, quatre propositions de réponses sont faites, dont une seule est exacte. Laquelle ?

\begin{enumerate}
\item Ludwig a pris quarante-cinq photos de son voyage en Allemagne et veut en imprimer cinq pour les mettre dans un cadre. Le nombre de possibilités de cadres pouvant être obtenu est:

\medskip

\begin{enumerate}
\begin{multicols}{4}
\item $5^{45}$ 
\item $45^5$
\item $\binom{45}{5}$ 
\item $A_{45}^5$
\end{multicols}
\end{enumerate}


\item D'une urne contenant cinquante boules numérotées de 1 et 50, on en extrait dix sans les remettre. On note les numéros ainsi obtenus sur un papier de sorte à avoir une suite. Le nombre de suites possibles est:

\medskip

\begin{enumerate}
\begin{multicols}{4}
\item $10^{50}$ 
\item $50^{10}$
\item $\binom{50}{10}$
\item $A_{50}^{10}$
\end{multicols}
\end{enumerate}

\item Dans le jeu télévisé \og Des chiffres et des lettres \fg, on demande huit fois aux candidats de choisir au hasard s'il veulent une voyelle ou une consonne. Le nombre de \og mots \fg{} possibles à l'issue de ces huit choix est:

\medskip

\begin{enumerate}
\begin{multicols}{4}
\item  $26!$ 
\item $26^8$
\item  $\binom{26}{8}$ 
\item $A_{26}^8$
\end{multicols}
\end{enumerate}


\item Le nombre d'anagrammes du mot \og STYLO \fg{} est:

\medskip

\begin{enumerate}
\begin{multicols}{4}
\item  $5!$
\item $5^5$
\item $\binom{26}{5}$
\item $A_{26}^5$
\end{multicols}
\end{enumerate}
\end{enumerate}

\tcblower

\begin{enumerate}
\item \textbf{Réponse (c)}. En effet, on choisit 5 éléments d'un ensemble de 45 éléments et l'ordre ne compte pas. Le nombre de sous-groupes de 5 éléments possibles est donc $\dbinom{45}{5}$.

\item \textbf{Réponse (d)}. En effet, on choisit 10 éléments d'un ensemble de 50 éléments et l'ordre compte. Il s'agit donc d'une arrangement. Le nombre de sous-groupe de 10 éléments possibles est donc $A_{50}^{10}$.

\item \textbf{Réponse (b)}. En effet, il y a 26 possibilités pour la première lettre, puis 26 pour la deuxième, etc. jusqu'à 26 possibilités pour la huitième. Il y a donc $26^8$ possibilités d'issues. Les issues sont des 8-uplets.

\medskip

\textit{Autre solution plus intuitive:} on peut énumérer tous les cas.
\begin{itemize}
\item \textbf{0 voyelle et 8 consonnes:} il y a $20^6$ possibilités.
\item \textbf{1 voyelle et 7 consonnes:} $6^1 \times 20^7 \times \dbinom{8}{1}$ (le coefficient binomial est là pour dire que l'on peut mettre la voyelle en 8 positions  différentes);
\item \textbf{2 voyelles et 6 consonnes:} $6^2\times20^6\times\dbinom{8}{2}$;
\item $\vdots$
\item  \textbf{8 voyelles et 0 consonne:} $6^8\times20^0\times\dbinom{8}{8}$.
\end{itemize}
Le nombre total de possibilités est donc la somme:
\[
\sum_{k=0}^8 6^k \times 20^{8-k} \times \dbinom{8}{k} = (6+20)^8
\]
d'après la formule du binôme de Newton. On arrive au même résultat que précédemment, à savoir $26^8$.

\item \textbf{Réponse (a)}. Il s'agit de compter le nombre d'anagrammes d'un mot où chaque lettre n'apparaît qu'une seule fois, donc il y en a $n!$, où $n$ est le nombre de lettres (donc ici : $5!$).
\end{enumerate}
\end{exocor}


%%%

\begin{exocor}{nombres de nombres binaires}[1]
Un \textit{octet} est une suite de huit chiffres (appelés \textit{bits}), chacun pris dans l'ensemble \{0;1\}, comme par exemple : $01101001$.

Combien y a-t-il d'octets différents ?

\tcblower

Un octet est composé de huit bits et il y a deux possibilités pour un bit : 0 ou 1. 

Il y a donc $2^8=256$ octets possibles.
\end{exocor}

%%% 

\begin{exocor}{mots de passe}[1]
Sur une plateforme numérique interne d'une société, on impose aux salariés la composition de leur mot de passe: il faut que ce dernier comporte:
\begin{itemize}
\item une lettre non accentuée prise dans l'alphabet latin (comportant 26 lettres), en majuscules ou minuscules;
\item un symbole parmi : \og \$ \fg, \og \# \fg, \og \& \fg, \og ? \fg et \og ! \fg ;
\item un chiffre compris entre 0 et 9 (inclus).
\end{itemize}

Le mot de passe est donc composé de trois caractères (comme: \og Z\#0 \fg).

Combien de mots de passe peuvent  ainsi être créés ?

\tcblower

Il y a $2\times26=52$ lettres possibles (si on compte les majuscules et les minuscules).

Ensuite, il y a $5$ possibilités pour le symbole et enfin, $10$ possibilités pour le chiffre pris parmi les dix disponibles.

Il y a donc $52 \times 5 \times 10 = \numprint{2600}$ possibilités pour un \og mot \fg{} de trois caractères. 

Il faut ensuite dénombrer les permutations du mot : il y en a $3!=6$.

\medskip

Ainsi, il y a $6 \times \numprint{2600}=\numprint{15600}$ mots de passe possibles.
\end{exocor}

%%%

\begin{exocor}{tournoi sportif}[1]
Lors d'un tournoi sportif, 12 équipes doivent affronter une fois les 11 autres.

Combien de matches doit-on organiser ?

\tcblower

L'équipe 1 doit affronter 11 équipes; il y a donc 11 matches à prévoir pour cette équipe.

L'équipe 2 doit affronter 10 équipes en plus de l'équipe 1 déjà comptée précédemment: 10 matches.

L'équipe 3 doit affronter 9 équipes en plus des équipes 1 et 2 déjà comptées: 9 matches.

Etc.

On voit alors que l'on doit prévoir $11+10+9+\cdots+1=\dfrac{11\times12}{2}=66$ matches.

\medskip

\textbf{Autre façon de voir:} il faut constituer des sous-ensembles de 2 équipes prises parmi les 12: il y a $\dbinom{12}{2}=66$ façons de procéder.
\end{exocor}


%%%

\begin{exocor}{mains d'un jeu de cartes}[2]
Un joueur dispose de cinq cartes prises parmi 52. On dit que c'est une \textit{main} de cinq cartes.
\begin{enumerate}
\item Combien de mains existent-il ?
\item Combien de mains ayant exactement un Roi existent-t-il ?
\item Combien de mains ayant exactement 2 Piques existent-il ?
\item Combien de mains ayant exactement 2 Piques et 1 C\oe ur existent-il ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item On choisit 5 cartes parmi 52 et l'ordre ne compte pas. Il s'agit donc ici d'une combinaison. 

Il y a donc $\dbinom{52}{5}=\dfrac{52!}{5!(52-5)!}=\numprint{2598960}$ mains possibles.

\item On impose dans cette question le fait qu'il y ait un Roi. Comme l'ordre ne compte pas, on peut considérer que la première est un Roi (il y a 4 choix possibles car il y a 4 Rois dans un jeu de cartes). Nous voulons exactement un Roi; par conséquent, il ne faut pas qu'il y en ait parmi les autres cartes : on choisit donc 4 cartes parmi les $52-4=48$ cartes qui ne sont pas des Rois.

Ainsi, il y a $4 \times \dbinom{48}{4}=\numprint{778320}$ mains comportant exactement un Roi.

\item Nous souhaitons ici exactement deux Piques. Comme l'ordre ne compte pas, on peut considérer que ce sont les deux premières cartes. Il y a $52\div4=13$ Piques donc il y a $\dbinom{13}{2}$ possibilités pour ces deux cartes. Pour les 3 autres cartes, il faut les choisir parmi les $52-13=39$ cartes restantes qui ne sont pas des Piques.

Ainsi, il y a $\dbinom{13}{2}\times\dbinom{39}{3}=\numprint{712842}$ mains possibles contenant exactement 2 Piques.

\item Nous souhaitons ici 2 Piques et 1 C\oe ur. Selon le même principe que celui utilisé dans la question précédente, on peut dire que le nombre de mains comportant exactement 2 Piques et 1 C\oe ur est égal à :
\[
\underbrace{\dbinom{13}{2}}_{2\text{ Piques}}\times\underbrace{\dbinom{13}{1}}_{1\text{ C\oe ur}}\times\underbrace{\dbinom{26}{2}}_{2\text{ autres}}=\numprint{329550}.
\]
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{s'assoir sur les chaises}[2]
Quatre garçons et trois filles doivent s'assoir en ligne sur sept chaises.
\begin{enumerate}
\item De combien de façons peuvent-ils s'assoir ?
\item Même question si les garçons et les filles doivent rester groupés.
\item Même question si les garçons et les filles doivent être disposés de façon alternée.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Il y a 7 personnes à permuter donc il y a $7!=\numprint{5040}$ façons de s'assoir.
\item Il y a deux groupes (filles et garçons), donc 2 façons de les disposer. Dans le groupe des filles, il y a $3!$ façons de les disposer et dans le groupe des garçons, il y en a $4!$.

Il y a donc $2 \times 3! \times 4! = 288$ façons de s'assoir.

\item Dans cette question, deux garçons ne peuvent pas être à côté, et deux filles non plus.

Imaginons que les chaises soient numérotées de 1 à 7. Supposons que les garçons s'assoient sur les chaises avec un numéro impair : il y a $4!$ façons de les disposer. De même, il y a $3!$ façons de disposer les filles sur les chaises dont le numéro est pair.

Au final, il y a $4! \times 3!=144$ façons de les assoir.
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{le congrès des gens polis}[2]
Chaque année, l'association des gens polis de Paris organise un congrès et comme chaque année, tous les participants doivent se serrer la main qu'une seule fois.

Cette année, il y a 50 participants.

Combien de poignées de mains vont être données ?

\tcblower

Il y a deux façons de raisonner pour cet exercice.

\begin{itemize}
\item \textit{Raisonnement combinatoire.}

Le nombre de poignées de mains est égal au nombre de sous-ensembles à deux éléments que l'on peut former dans un ensemble à 50 d'éléments, à savoir $\dbinom{50}{2}=\numprint{1225}$.

Il y a donc \numprint{1225} poignées de mains.

\newpage

\item \textit{Analyse numérique.}

Le premier participant peut serrer la main à 49 personnes. Ensuite, le deuxième peut serrer la main aux 48 personnes restantes. Le troisième peut serrer la main aux 47 autres, etc. jusqu'aux deux dernières personnes qui ne peuvent donner qu'une poignée de mains.

Il y a donc $49+48+47+\cdots+2+1$ poignées de mains possibles. Or,
\[
1+2+3+\cdots+n=\dfrac{n(n+1)}{2}.
\]
Il y a donc $\dfrac{49\times50}{2}=\numprint{1225}$ poignées de mains.
\end{itemize}
\end{exocor}

%%%

\begin{exocor}{le clavier à neuf touches}[2]
Un clavier comporte neuf touches : 1, 2, 3, 4, 5, 6, A, B et C.

Un \textit{code} obtenu à l'aide de ce clavier est une suite d'une lettre et de trois chiffres.

\begin{enumerate}
\item Combien de codes différents peut-on former ?
\item Combien y a-t-il de codes sans le chiffre \og 1 \fg ?
\item Combien y a-t-il de codes comportant au moins une fois le chiffre \og 1 \fg ?
\item Combien y a-t-il de codes comportant des chiffres distincts ?
\item Combien y a-t-il de codes comportant au moins deux chiffres identiques ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Il y a 3 lettres possibles pour la première entrée (le premier caractère du code) et on a le choix entre 6 chiffres pour chacun des 3 chiffres suivants.

Il y a donc $3\times 6^3=648$ codes possibles.

\item Il y a toujours 3 lettres possibles pour la première entrée, puis 5 choix possibles pour chacun des 3 autres entrées.

Il y a donc $3 \times 5^3 = 375$ codes sans \og 1 \fg.


\item Il y a encore 3 lettres possibles pour la première entrée. Ensuite, on peut raisonner par contradiction : nous avons vu aux questions précédentes qu'il existe 375 codes sans le chiffre \og 1 \fg{} et qu'il y a 648 codes possibles. 

Il y a donc $648-375=273$ codes ayant au moins un chiffre \og 1 \fg.

\item Il y a 3 lettres possibles pour la première entrée, et il faut compter le nombre d'arrangements de 3 éléments pris parmi 6 pour avoir un code où tous les chiffres sont distincts (l'ordre compte et on peut assimiler ceci à un tirage sans remise, ce qui justifie que c'est bien un arrangement).

Il y a donc $3 \times A_6^3 = 3 \times \dfrac{6!}{3!}=360$ codes possibles où tous les chiffres sont distincts.

\item Ici encore, on raisonne par contradiction : le contraire de l'événement \og le code comporte au moins deux chiffres identiques \fg{} et l'événement : \og le code comporte des chiffres distincts \fg.

Il y a donc $648-360=288$ codes comportant au moins deux chiffres identiques.
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{nombre de mots}[2]
Un programme permet de générer un mot de 1 à 10 lettres en choisissant aléatoirement chacune des lettres dans un alphabet en comportant 26.

\medskip

Déterminer un ordre de grandeur du nombre de mots possibles.

\tcblower

\begin{itemize}
\item Si le mot généré ne contient qu'une lettre alors il y a 26 possibilités.
\item Si le mot contient deux lettres alors il y a $26^2$ possibilités.
\item Si le mot contient trois lettres alors il y a $26^3$ possibilités.
\item $\vdots$
\item Si le mot contient dix lettres alors il y a $26^{10}$ possibilités.
\end{itemize}

Ainsi, le nombre total de mots possibles est:
\[
26+26^2+26^3+\cdots+26^{10}.
\]

Pour rappel, si $(u_n)$ est une suite géométrique de raison $q\neq1$ alors:
\[
u_0+u_1+u_2+\cdots+u_n=u_0\times\dfrac{q^{n+1}-1}{q-1}.
\]
La somme que nous souhaitons calculer est la somme des premiers termes de la suite géométrique $(u_n)$ de premier terme $u_0=26$ et de raison $q=26$. 
Ainsi, 
\begin{align*}
26+26^2+26^3+\cdots+26^{10} & = 26\times\dfrac{26^{10}-1}{26-1}\\
& \approx 1,5 \times 10^{14}.
\end{align*}
\end{exocor}

%%% 

\newpage

\begin{exocor}{réponses possibles à un QCM}[2]
Un QCM est composé de 20 questions. Chacune d'elles propose 4 réponses possibles, dont une seule est correcte.

Un·e élève répond au hasard à toutes les questions.

\begin{enumerate}
\item Combien y a-t-il de façons de répondre à ce QCM ?\item Combien y a-t-il de possibilités où exactement 5 réponses sont correctes ?
\item Combien y a-t-il de possibilités où au moins 10 réponses sont correctes ?
\item Quelle est alors la probabilité d'avoir au moins 10 bonnes réponses en répondant au hasard à chacune des questions de ce QCM ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Il y a 4 façons de répondre pour chacune des 20 questions. C'est une 20-uplets sur un ensemble à 4 éléments (les 4 propositions).

\underline{Donc il y a $4^{20}=\numprint{1099511627776}$ façons de répondre à ce QCM.}

\item Dans cette question, il ne doit y avoir que 5 bonnes réponses; celles-ci peuvent être en n'importe quelles positions parmi les 20 questions. Il y a donc $\dbinom{20}{5}$ possibilités pour ces 5 réponses correctes.

Les 15 autres questions doivent être fausses; il y a donc 3 choix possibles pour chacune des 15 questions restantes, soit $3^{15}$ possibilités.


D'après le principe multiplicatif, il y a alors $\dbinom{20}{5}\times3^{15}$ façons de répondre pour avoir 5 bonnes réponses.

\newpage

\item D'après ce que nous avons dit à la question précédente, il y a $\dbinom{20}{k}\times 3^{20-k}$ façons de répondre pour avoir $k$ bonnes réponses.

D'après le principe additif, le nombre de façons de répondre afin d'avoir au moins 10 bonnes réponses est égal à:
\[
\sum_{k=10}^{20} \dbinom{20}{k}\times 3^{20-k} = \numprint{15244087642}.
\]

\item La probabilité d'avoir au moins 10 bonnes réponses en répondant au hasard à chacune des questions de ce QCM est donc égale à :
\[
\dfrac{\numprint{15244087642}}{\numprint{1099511627776}}\approx0,014.
\]
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{les groupes d'échecs}[2]
Roméo et Juliette sont dans une équipe d'échecs composée de 15 personnes (dont elles).

Pour participer à un grand concours, un groupe de 6 personnes doit être formé.

\begin{enumerate}
\item Combien de groupes différents peut-on former ?
\item Combien de groupes contenant Roméo et Juliette peut-on former ?
\item Combien de groupes ne contenant que Roméo ou que Juliette peut-on former ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item On doit ici constituer un groupe de 6 personnes prises parmi les 15; c'est donc une combinaison. Il y a donc $\dbinom{15}{6}=\numprint{5005}$ groupes possibles.

\item Roméo et Juliette doivent nécessairement être dans le groupe, donc cela revient à constituer un groupe de 4 élèves (en plus de Roméo et Juliette) parmi les $15-2=13$ élèves restant.

Il y a donc $\dbinom{13}{4}=715$ groupes possibles.

\item On ne souhaite ici dénombrer que les groupes ne contenant que Roméo et les groupes ne contenant que Juliette.

Pour les groupes ne contenant que Roméo ou Juliette, il y en a $\dbinom{2}{1}=2$. Il y a ensuite $\dbinom{13}{5}$ façons de placer les 13 autres personnes. Il y a donc $\dbinom{2}{1}\times\dbinom{13}{5}=\numprint{2574}$ groupes ne contenant que Roméo ou que Juliette.
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{le jeu du Tarot}[2]
Un jeu de tarot contient 78 cartes:
\begin{itemize}
\item 21 atouts, 
\item la carte que l'on appelle l'\textit{excuse},
\item 14 cartes de chacune des 4 couleurs (cœur, pique, trèfle et carreau).
\end{itemize}
\begin{enumerate}
\item Combien de tirages simultanés de six cartes d'un tel jeu peut-on obtenir contenant deux atouts et quatre trèfles ?
\item Combien de tirages simultanés de six cartes d'un tel jeu peut-on obtenir contenant exactement un atout et au moins trois as ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item \textbf{Deux atouts et quatre trèfles.}

Ici, nous sommes dans un schéma classique: il y a $\dbinom{21}{2}$ possibilités de choisir deux atouts et $\dbinom{14}{4}$ possibilités de choisir quatre trèfles.

il y a donc:
\[
\dbinom{21}{2}\times\dbinom{14}{4}=\numprint{210210}
\]
tirages possibles.

\newpage

\item \textbf{Exactement un atout et au moins trois as.}

\begin{itemize}
\item \textit{Nombre de tirages contenant exactement un atout et exactement 3 as:}
\[
\dbinom{21}{1}\times\dbinom{4}{3}\dbinom{78-21-4}{2}=\numprint{115752}.
\]
\item \textit{Nombre de tirages contenant exactement un atout et exactement 4 as:}
\[
\dbinom{21}{1}\times\dbinom{4}{4}\dbinom{78-21-4}{1}=\numprint{1113}.
\]
\end{itemize}
Il y a donc $\numprint{115752}+\numprint{1113}=\numprint{116865}$ tirages correspondant à ce que l'on veut.
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{une puce sur une grille}[2]
Une puce se trouve sur une grille $n \times p$ en bas à gauche et compte rejoindre le point le plus à droite en haut en utilisant un chemin de distance minimale (donc de longueur $n+p$).
\begin{center}
\begin{tikzpicture}
\draw[gray,dashed] (0,0) grid (5,3);
\draw[red,thick,->,>=latex] (0,0) -- (2,0) -- (2,1) -- (3,1) -- (3,3) -- (5,3);
\draw [decorate,decoration = {calligraphic brace,amplitude=10pt,raise=3pt}] (5,-.5) --  (0,-.5);
\node[below] at (2.5,-1) {$n$};
\draw [decorate,decoration = {calligraphic brace,amplitude=10pt,raise=3pt}] (5.5,3) --  (5.5,0);
\node[right] at (6,1.5) {$p$};
\end{tikzpicture}
\end{center}
Combien y a-t-il de chemins possibles ?
\vspace*{-1.3em}

\tcblower

Symbolisons par \og D \fg{} le mouvement de la puce qui consiste à se déplacer vers la droite d'une unité, et par \og H \fg{} le déplacement d'une unité vers le haut.

Le mouvement final est donc représenté par une succession de $n+p$ \og D \fg{} et \og H \fg, comme par exemple: \og DDHDHHDD \fg{} pour représenter le déplacement donné en exemple :
\begin{center}
\begin{tikzpicture}[scale=0.8]
\draw[gray,dashed] (0,0) grid (5,3);
\draw[red,thick,->,>=latex] (0,0) -- (2,0) -- (2,1) -- (3,1) -- (3,3) -- (5,3);
\draw [decorate,decoration = {calligraphic brace,amplitude=10pt,raise=3pt}] (5,-.5) --  (0,-.5);
\node[below] at (2.5,-1) {$n$};
\draw [decorate,decoration = {calligraphic brace,amplitude=10pt,raise=3pt}] (5.5,3) --  (5.5,0);
\node[right] at (6,1.5) {$p$};
\end{tikzpicture}
\end{center}
La question revient donc à trouver le nombre d'anagrammes de ce \og mot \fg{} de $n+p$ lettres.

D'après la méthode donnée dans le corrigé de l'exercice
\ref{exercice:\thechapter.13}, il y en a:
\[
\dfrac{\fact{(n+p)}}{\fact{n}\fact{p}}.
\]
\end{exocor}

%%%

\begin{exocor}{alternance entre pairs et impairs}[2]
Une urne contient $2n$ boules numérotées de 1 à $2n$ qu'on tire \textit{successivement sans remise}. 

Combien de tirages peut-on faire pour lesquels un numéro pair est toujours suivi d'un numéro impair et un numéro impair d'un numéro pair ?

\tcblower

\begin{itemize}
\item \textbf{Tirages dont la première boule porte un numéro pair.}

Il y a $n$ nombres pairs donc il y a $n$ tirages commençant par un nombre pair. 

Il y a ensuite $n$ nombres impairs possibles pour le deuxième numéro.

Pour le troisième numéro, on a le choix entre $(n-1)$ nombres pairs; idem pour le quatrième.

etc.

Il y a donc $\fact{n} \times \fact{n}$ tirages dont le premier numéro est pair.

\newpage
\item \textbf{Tirages dont la première boule porte un numéro impair.}

Le raisonnement est le même que précédemment: il y a $\fact{n} \times \fact{n}$ tirages dont le premier numéro est impair.

\item Par conséquent, il y a $2\big(\fact{n}\big)^2$ tirages possibles.
\end{itemize}
\end{exocor}

%%%

\begin{exocor}{$n$ urnes}[3]
On dispose de $n$ urnes numérotées de 1 à $n$ dont chacune peut accueillir autant de boules que l'on veut. 

De combien de manières peut-on y ranger $p$ boules indiscernables ?

\tcblower

Notons $u_k$ le nombre de boules dans l'urne $k$, $1\leqslant k \leqslant n$.

Décidons alors de représenter les situations possibles par le mot:
\[
\underbrace{B\ldots B}_{u_1\text{ lettres }B}S\underbrace{B\ldots B}_{u_2\text{ lettres }B}S\cdots S\underbrace{B\ldots B}_{u_n\text{ lettres }B}
\]
La lettre \og B \fg{} désigne une boule et \og S \fg{} désigne une séparation entre les urnes pour bien les distinguer.

Répondre à la question posée revient à trouver toutes les anagrammes du mot contenant $n$ \og B \fg{} (car il y a $n$ boules) et $(p-1)$ \og S \fg.

La réponse est donc:
\[
\dfrac{\fact{(n+p-1)}}{\fact{n}\fact{(p-1)}}.
\]  
\end{exocor}

%%%

\begin{exocor}{formule de Vandermonde}[3]
Montrer que:
\[
\forall n\in\N,\quad \sum_{k=0}^n\dbinom{n}{k}^2 = \dbinom{2n}{n}.
\]
On pourra pour cela considérer $(x+1)^{2n}$ et son développement.

\tcblower

D'après la formule du binôme de Newton:
\[
(x+1)^{2n} = \sum_{k=0}^{2n} \dbinom{2n}{k}x^k.
\]
Ainsi, le coefficient de degré $n$ du développement de $(x+1)^{2n}$ est égal à $\dbinom{2n}{n}$.

\medskip

Nous pouvons aussi écrire:
\[
(x+1)^{2n} = \big((x+1)^n\big)^2 = \left( \sum_{k=0}^{n} \dbinom{n}{k}x^k \right)^2.
\]
Ainsi, le coefficient de degré $n$ du développement de $(x+1)^{2n}$ est égal à $\displaystyle\sum_{k=0}^n\dbinom{n}{k}\dbinom{n}{n-k}$.

Or, $\dbinom{n}{n-k}=\dbinom{n}{k}$.

Donc ce coefficient vaut finalement  $\displaystyle\sum_{k=0}^n\dbinom{n}{k}^2$.

\medskip

D'où l'égalité demandée.

\begin{rem}
Par un raisonnement analogue; on peut aussi montrer l'égalité suivante:
\[
\forall n\in\N,\quad\sum_{k=0}^{n} \dbinom{n}{k}\dbinom{2n}{k} = \dbinom{3n}{n}.
\]
\end{rem}
\end{exocor}


%%%

\begin{exocor}{anagrammes} [3]
\begin{enumerate}
\item Combien d'anagrammes y a-t-il au mot \og ABYME \fg{} ?
\item Combien d'anagrammes différentes y a-t-il au mot \og NAPPE \fg{} ?
\item Combien d'anagrammes différentes y a-t-il au mot \og KAYAK \fg{} ?
\item Combien d'anagrammes différentes y a-t-il au mot \og UBUESQUE \fg{} ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le mot \og ABYME \fg{} contient cinq lettres distinctes. Le nombre d'anagrammes est donc égal au nombre de permutations de ces cinq lettres.

Il y a donc $5!=120$ anagrammes au mot \og ABYME \fg.

\item Le mot \og NAPPE \fg{}  contient cinq lettres, mais elles ne sont pas toutes distinctes : il y a quatre lettres distinctes. 

Ainsi, parmi les 120 permutations, il y en a qui sont identiques. Comme il y a deux lettres identiques, il y aura deux fois les mêmes permutations (par exemple \og P$_1$P$_2$NAE \fg{} et \og P$_2$P$_1$NAE \fg{} donnent l'anagramme \og PPNAE \fg). Il faut donc diviser par 2 le nombre de permutations.

Il y a donc $\dfrac{5!}{2}=60$ anagrammes différentes au mot \og NAPPE \fg.

\item Le mot \og KAYAK \fg{} comporte cinq lettres dont trois sont distinctes.

Selon le même principe expliqué à la question précédente, il faut diviser les 120 permutations par 2 (car il y a deux \og K \fg) et encore par 2 (car il y a deux \og A \fg).

Il y a donc $\dfrac{5!}{2\times2}=30$ anagrammes différentes au mot \og KAYAK \fg.

\item Le mot \og UBUESQUE \fg{} comporte huit lettres dont deux sont répétées : le \og U \fg{} est présent trois fois et le \og E \fg{} l'est deux fois. S'il faut diviser le nombre de permutations par 2 (car il y a deux \og E \fg), il ne suffit pas de diviser encore par 3 car il y a trois \og U \fg. En effet, il faut diviser par $3!=6$.

Pour mieux comprendre ceci, on peut prendre l'exemple du mot \og AAAB \fg{} qui admet théoriquement $4!=4\times3\times2$ permutations et qui admet pour anagrammes : \og AAAB \fg, \og AABA \fg, \og ABAA \fg{} et \og BAAA \fg. Il y en a donc $4=\dfrac{4\times3\times2}{3\times2}=\dfrac{4!}{3!}$.

\medskip

Ainsi, il y a $\dfrac{8!}{2 \times 3!}=\numprint{3360}$ anagrammes différentes au mot \og UBUESQUE \fg.
\end{enumerate}

\begin{methode}[non officiellement au programme]
Si un mot de $n$ lettres comporte $k$ lettres identiques, il y a $\dfrac{n!}{k!}$ anagrammes différentes de ce mot. 

S'il comporte $k$ lettres identiques et $p$ autres lettres identiques différentes des premières alors il y a $\dfrac{n!}{k! \times p!}$ anagrammes différentes.
\end{methode}

\begin{rem}
On peut raisonner différemment en disant que trouver une anagramme du mot revient à :
\begin{itemize}
\item placer 3 lettres \og U \fg{} parmi les 8 positions possibles : il y a $\binom{8}{3}$ possibilités;
\item placer 2 lettres \og E \fg{} parmi les $8-3=5$ positions restantes : il y a $\binom{5}{2}$ possibilités;
\item trouver le nombre d'anagrammes sur les $5-2=3$ lettre restantes : il y a $3!$ possibilités.
\end{itemize}
On arrive alors à $\dbinom{8}{3}\times\dbinom{5}{2}\times3!=\numprint{3360}$ anagrammes différentes.
\end{rem}
\end{exocor}

%%%

\begin{exocor}{nombre d'atomes}[3]
On estime à $10^{79}$ le nombre d'atomes dans l'Univers visible.

Combien de cartes différentes devrait avoir un jeu pour que le nombre de permutations possibles dépasse cette valeur ? \textit{Conseil :} n'ayez pas peur de prendre des initiatives!

\tcblower

Notons $n$ le nombre de cartes différentes. Le nombre de permutations est alors égal à $n!$.

Il faut donc résoudre l'inéquation:
\[
n! \geqslant 10^{79}.
\]

Pour résoudre cette inéquation, on peut faire appel au logarithme népérien:
\begin{align*}
n! \geqslant 10^{79} & \iff \ln(n!) \geqslant \ln\big(10^{79}\big)\\
& \iff \ln(1)+\ln(2)+\ln(3)+\cdots+\ln(n) \geqslant 79\ln(10).
\end{align*}

On peut alors faire appel à un programme Python pour déterminer la première valeur de $n$ pour laquelle l'inégalité est vraie.

\begin{python}
from math import log
n = 1
s = 0
while s < 79*log(10):
    n += 1
    s += log(n)
print(n)
\end{python}

\medskip

Ce programme affiche la valeur \og 59 \fg.

\medskip

Il faut donc que le jeu comporte 59 cartes différentes pour que le nombre de permutations dépasse le nombre d'atomes dans l'Univers visible.

\newpage

Si vous n'avez pas encore vu la notion de logarithme népérien, le programme suivant affiche aussi \og 59 \fg: 

\begin{python}
f,n = 1,1
while f < 10**79:
    n += 1
    f *= n
print(n)
\end{python}

\begin{rem}
Remplacez \og 79 \fg{} par \og \numprint{1000} \fg{} dans les deux programmes et vous verrez pourquoi le premier est plus intéressant...

\textit{Spoiler alert} : le second risque de prendre pas mal de temps, même avec un bon processeur !
\end{rem}
\end{exocor}

%%%

\begin{exocor}{constituer des groupes}[3]
\begin{enumerate}
\item \mbox{De combien de façons peut-on partager 12 personnes en trois groupes, un groupe de 2 et deux groupes de 5 ?}
\item Même question avec trois groupes de 4 personnes.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Avant de traiter l'exercice, on peut pendre l'exemple d'un groupe de 4 personnes, notées $a$, $b$, $c$ et $d$. Si on veut constituer deux groupes de deux personnes, on a les possibilités page suivante.

\medskip

\begin{center}
\begin{tabular}{|Sc|Sc|}
\rowcolor{corrigenumbg}\hline
\color{corrigepage}Groupe 1 &\color{corrigepage} Groupe 2\\
\hline
$a$ avec $b$ & $c$ avec $d$\\
\hline
$a$ avec $c$ & $b$ avec $d$\\
\hline
$a$ avec $d$ & $b$ avec $c$\\
\hline
\end{tabular}
\end{center}

\medskip

Il y a seulement 3 possibilités alors que nos calculs nous pousseraient peut-être à dire qu'il y en a $\binom{4}{2}\times\binom{2}{2}=6$ (on choisit 2 personnes parmi les 4 pour constituer le premier groupe et pour le second, on en choisit 2 parmi les deux restantes). Avec cette dernière méthode, il faut comprendre que l'on considère que les cas  \og Groupe 1 : $a$ avec $b$, Groupe 2 : $c$ avec $d$ \fg{} et \og Groupe 1 : $c$ avec $d$, Groupe 2 : $a$ avec $b$ \fg{}  sont distincts alors que non. Il faut donc diviser par deux le nombre de possibilités trouvés par cette méthode.

\medskip


Revenons maintenant à notre exercice : il y a $\binom{12}{2}$ façons de constituer un groupe de 2 personnes prises parmi les 12, puis $\binom{10}{5}$ façons de constituer un autre groupe de 5 personnes prises parmi les 10 restantes, et enfin une seule façon de constituer le dernier groupe de 5 personnes.

Le nombre total de groupes possibles est donc :
$\dfrac{\dbinom{12}{2}\times\dbinom{10}{5}}{2}=\numprint{8316}$.

\item Pour cette question encore, prenons un cas simple. Considérons un groupe de 6 personnes, notées $a$, $b$, $c$, $d$, $e$ et $f$, que l'on souhaite partager en groupes de 2. Les différents groupes possibles sont donnés dans le tableau suivant:

\begin{center}
\begin{tabular}{|Sc|Sc|Sc|}
\rowcolor{corrigenumbg}\hline
\color{corrigepage}Groupe 1 & \color{corrigepage}Groupe 2 &\color{corrigepage} Groupe 3\\
\hline
\multirow{3}{*}{\color{red}$a$ avec $b$} & \color{red}$c$ avec $d$ & \color{red}$e$ avec $f$\\\cline{2-3}
& \color{red}$c$ avec $e$ & \color{red}$d$ avec $f$\\\cline{2-3}
& \color{red}$c$ avec $f$ & \color{red}$d$ avec $e$\\
\hline
\multirow{3}{*}{\color{red}$a$ avec $c$} & \color{red}$b$ avec $d$ & $e$ avec $f$\\\cline{2-3}
& \color{red}$b$ avec $e$ & $d$ avec $f$\\\cline{2-3}
& \color{red}$b$ avec $f$ & $d$ avec $e$\\
\hline
\end{tabular}\\
$\vdots$\\
$\downarrow$

\begin{tabular}{|Sc|Sc|Sc|}
\rowcolor{corrigenumbg}\hline
\color{corrigepage}Groupe 1 & \color{corrigepage}Groupe 2 &\color{corrigepage} Groupe 3\\
\hline
\multirow{3}{*}{\color{red}$a$ avec $d$} & \color{red}$b$ avec $c$ & $e$ avec $f$\\\cline{2-3}
& $b$ avec $e$ & $c$ avec $f$\\\cline{2-3}
& $b$ avec $f$ & $c$ avec $e$\\
\hline
\multirow{3}{*}{\color{red}$a$ avec $e$} & $b$ avec $c$ & $d$ avec $f$\\\cline{2-3}
& $b$ avec $d$ & $c$ avec $f$\\\cline{2-3}
& $b$ avec $f$ & $c$ avec $d$\\
\hline
\multirow{3}{*}{\color{red}$a$ avec $f$} & $b$ avec $c$ & $d$ avec $e$\\\cline{2-3}
& $b$ avec $d$ & $c$ avec $e$\\\cline{2-3}
& $b$ avec $e$ & $c$ avec $d$\\
\hline
\end{tabular}
\end{center}

\medskip

Nous avons mis en rouge les groupes distincts : il y en a 15. Or, avec une méthode de dénombrement \og classique \fg, on obtiendrait :
\[
\dbinom{6}{2}\times\dbinom{4}{2}\times\dbinom{2}{2}=90\text{ groupes possibles.}
\]
Le nombre de groupes possibles est donc égal à :
\[
\dfrac{\dbinom{6}{2}\times\dbinom{4}{2}\times\dbinom{2}{2}}{6}=\dfrac{\dbinom{6}{2}\times\dbinom{4}{2}\times\dbinom{2}{2}}{3!}.
\]
Revenons maintenant à notre exercice : nous voulons constituer 3 groupes de 4 personnes, ce qui nous amène au calcul suivant:
\[
\dfrac{\dbinom{12}{4}\times\dbinom{8}{4}\times\dbinom{4}{4}}{3!}=\numprint{5775}.
\]
Il y a donc \numprint{5775} groupes possibles.
\end{enumerate}
\end{exocor}


\newpage

\sectionnn{Objectif bac}

%%%

\begin{exocor}{Extraits de divers sujets 2025}[1]
\textit{Pour chacune des affirmations suivantes, indiquer si elle est vraie ou fausse.\\ Chaque réponse doit être justifiée. Une réponse non justifiée ne rapporte aucun point.}

\begin{enumerate}
\item Soient $E$ et $F$ les ensembles: $E = \{1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7\}\text{ et } F = \{0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9\}$.

\textbf{Affirmation 1 :} il y a davantage de 3-uplets d'éléments distincts de $E$ que de combinaisons à 4 éléments de $F$.

\medskip

\item Dans une classe de terminale, il y a 18 filles et 14 garçons.

On constitue une équipe de volley-ball en choisissant au hasard 3 filles et 3 garçons.

\textbf{Affirmation 2:} il y a \numprint{297024} possibilités pour former une telle équipe.

\medskip

\item Lorsqu'une personne achète son billet en ligne, un code de validation lui est envoyé par SMS afin qu'elle confirme son achat.

Ce code est généré de façon aléatoire et est constitué de 4 chiffres deux à deux
distincts, le premier chiffre étant différent de 0.

\textbf{Affirmation 3:} le nombre de codes différents pouvant être générés est \numprint{5040}.

\medskip

\item Deux équipes de footballeurs de 22 et 25 joueurs échangent une poignée de main à la fin d'un match. Chaque joueur d'une équipe serre une seule fois la main de chaque joueur de l' autre équipe.

\textbf{Affirmation 4:} 47 poignées demains ont été échangées.

\medskip

\item Une course oppose 18 concurrents. On récompense indistinctement les trois premiers en offrant le même prix à chacun.

\textbf{Affirmation 5:} il y a \numprint{4896} possibilités de distribuer ces prix.

\medskip

\item Une association organise une compétition de course de haies qui permettra d'établir un podium (le podium est constitué des trois meilleurs sportifs classés dans leur ordre d'arrivée). Sept sportifs participent au tournoi. Jacques est l'un d'entre eux.

\textbf{Affirmation 6:} il y a 90 podiums différents dont Jacques fait partie.

\medskip

\item Une anagramme d'un mot est le résultat d'une permutation des lettres de ce mot.

Exemple : le mot BAC est possède 6 anagrammes : BAC, BCA, ABC, ACB, CAB, CBA. 

\textbf{Affirmation 7:} le mot EULER possède 120 anagrammes.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Il y a 7 éléments dans $E$, donc il y a $7^3=343$ 3-uplets d'éléments distincts de $E$.

Il y a 10 éléments dans $F$ donc il y a $\dbinom{10}{4}=210$ combinaisons à 4 éléments de $F$.

\underline{Finalement, l'affirmation 1 est vraie.}

\medskip

\item On souhaite ici constituer un groupe de 3 filles (prises parmi 18) et de 3 garçons (pris parmi 14). L'ordre ne compte pas donc le nombre d'équipes est:
\[
\dbinom{3}{18}\times\dfrac{14}{3}=\numprint{297024}.
\]
\underline{L'affirmation 2 est donc vraie.}

\medskip

\item Le code à 4 chiffres doit comporter 4 chiffres distincts, le premier chiffre étant différent de 0.
On a donc le choix entre:
\begin{itemize}
\item 9 chiffres pour le premier (de 1 à 9);
\item 9 chiffres pour le deuxième (0 et les 8 autres qu'il reste si on exclut le premier choisi);
\item 8 chiffres pour le troisième (en excluant les deux qui ont été choisis pour le premier et le deuxième chiffre du code);
\item 7 chiffres pour le quatrième.
\end{itemize}
Le nombre de codes possibles est donc:
\[
9 \times 9 \times 8 \times 7 = \numprint{4536}.
\]
\underline{L'affirmation 3 est donc fausse.}

\medskip

\item Chaque joueur de l'équipe ayant 22 joueurs serre la main de chaque joueur de l'autre équipe (avec 25 joueurs). Il s'agit donc d'un \textit{produit cartésien}.

Il; y a donc $22 \times 25 = 550$ poignées de mains.

\underline{L'affirmation 4 est donc fausse.}

\medskip

\item On cherche ici non pas un \textit{podium} mais un groupe de 3 personnes parmi les 18 concurrents. Il y  a donc
\[
\dbinom{18}{3} = \numprint{816}
\]
groupes possibles.

\underline{L'affirmation 5 est donc fausse.}

\medskip

\item On impose ici que Jacques fasse partie du podium. Il reste donc 2 places. On cherche donc un arrangement à deux éléments dans un ensemble à seulement 6 éléments (le groupe total auquel on enlève Jacques). Il y a donc:
\[
6 \times 5 = 30
\]
possibilités.

Mais il nous reste à placer Jacques, et il y a $\dbinom{1}{3}=3$ manières de le placer.

Finalement, il y a $30 \times3 = 90$ podiums possibles.

\underline{L'affirmation 6 est donc vraie.}

\medskip

\item Une anagramme du mot EULER est une permutation: il y en aurait 5! si l'on distinguait les deux \og E \fg, ce qui n'est pas le cas. On les compte donc deux fois en prenant 5! anagrammes.

Finalement, il y a $\dfrac{5!}{2}=60$ anagrammes au mot EULER.

\underline{L'affirmation 7 est donc fausse.} 
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{Extrait du sujet 2 d'Afrique du sud, novembre 2025}[1]
On considère l'ensemble des nombres entiers relatifs non nuls compris entre $-30$ et 30; cet ensemble peut s'écrire ainsi : 
\[
\{
-30; -29; -28; \ldots; -1 ; 1 ; \ldots ; 28 ; 29 ; 30 
\}.
\]
Il comporte 60 éléments.

On choisit dans cet ensemble successivement et sans remise un entier relatif $a$ puis un entier relatif $c$.
\begin{enumerate}
\item Combien de couples \coord{a}{c} différents peut-on ainsi obtenir ?
\end{enumerate}
On considère l'événement:
\begin{center}
$M$ : \og l'équation $ax^2+bc+c=0$ possède deux solutions réelles distinctes \fg,
\end{center}
où $a$ et $c$ sont les entiers relatifs précédemment choisis.
\begin{enumerate}[resume]
\item Montrer que l'événement $M$ a lieu si et seulement si $ac < 1$.
\item Expliquer pourquoi l'événement contraire $\evcont{M}$ comporte \numprint{1740} issues.
\item Quelle est la probabilité de l'événement $M$? On arrondira le résultat à $10^{-2}$.
\end{enumerate}

\tcblower

\begin{enumerate}
\item On a le choix entre 60 entiers pour le premier nombre $a$.

Il n'y a pas de remise (donc $a \neq c$); il y a donc 59 choix possibles pour $c$.

\underline{Il y a donc $60 \times 59 = \numprint{3540}$ couples différents.}

\item L'équation a deux racines réelles distinctes si et seulement si le discriminant est supérieur à zéro:
\[
\Delta = 4 - 4ac > 0 \iff 4(1 - ac) >0 \iff 1 - ac > 0 \iff ac < 1.
\]

\item $\evcont{M} \iff ac \geqslant 1$.

Il faut donc trouver le nombre de couples vérifiant $ac \geqslant 1$, mais en fait $ac > 1$ puisque l'on ne peut avoir $\coord{-1}{-1}$ ni $\coord{1}{1}$.

Si l'on choisit en premier un entier négatif (30 choix), le second terme sera choisi dans les 29 entiers négatifs restant, soit $30 \times 29 = 870$ couples.

Il en est de même si les deux termes choisis sont positifs.

L'événement $\overline{M}$ sera réalisé pour $870 + 870 = \numprint{1740}$ couples.

\item D'après le résultat précédent, l'événement $M$ sera réalisé pour $\numprint{3540} - \numprint{1740} = \numprint{1800}$ couples.

Donc:
\[
p(M) = \dfrac{\numprint{1800}}{\numprint{3540}} = \dfrac{30}{59} \approx \numprint{0,51}.
\]
\end{enumerate}
\vspace*{2cm}
\end{exocor}

%%%

\begin{exocor}{événement d'une entreprise}[2]
Une entreprise organise un événement où 8 personnes sont invitées, dont 4 hommes et 4 femmes. On cherche à former des groupes et des équipes pour différentes activités.

\bigskip

\partie{A: formation d'un groupe}

\begin{enumerate}
\item Combien de manières différentes peut-on former un groupe de 5 personnes parmi les 8 personnes invitées, sans distinction de sexe ?
\item Combien de manières différentes peut-on former un groupe de 5 personnes qui contient exactement 3 hommes et 2 femmes ?
\end{enumerate}

\medskip

\partie{B : ordre et sélection}

Lors d'un jeu, 3 personnes sont sélectionnées parmi les 8 invitées et elles doivent être classées en fonction de leur performance.
\begin{enumerate}
\item Combien de façons différentes peut-on choisir et classer ces 3 personnes ?
\item Dans combien de cas le classement est composé de 2 femmes et 1 homme ?
\end{enumerate}

\bigskip


\partie{C : organisation d'une activité}

Pour une autre activité, 3 personnes sont tirées au sort parmi les 8 invités, mais cette fois l'ordre dans lequel elles sont choisies importe.
\begin{enumerate}
\item Combien de listes ordonnées (p-uplets) de 3 personnes peut-on former parmi les 8 invités ?
\item Quelle est la probabilité que les 3 personnes choisies soient toutes des femmes ?
\end{enumerate}

\bigskip

\partie{D : cas pratique}

L'organisateur veut constituer une équipe de 4 personnes, mais avec certaines contraintes :
\begin{itemize}
\item L'équipe doit comporter au moins une femme.
\item L'ordre n'a pas d'importance dans la composition de cette équipe.
\end{itemize}

Combien de façons différentes peut-il former une telle équipe ?

\tcblower

\medskip

\partie{A}

\begin{enumerate}
\item On cherche à former un groupe de 5 personnes parmi 8, sans distinction de sexe. Le nombre de combinaisons possibles est donné par : $
\dbinom{8}{5} = 56$.

\underline{Il y a donc 56 façons de former ce groupe.}

\item Pour former un groupe de 5 personnes comprenant exactement 3 hommes et 2 femmes, on doit d'abord choisir 3 hommes parmi les 4, puis 2 femmes parmi les 4 :
\[
\binom{4}{3} \times \binom{4}{2} = 4 \times 6 = 24.
\]
\underline{Il y a donc 24 façons de former ce groupe.}
\end{enumerate}

\medskip

\partie{B}

\begin{enumerate}
\item Si l'on doit choisir et classer 3 personnes parmi les 8 invités, le nombre d'arrangements est donné par :
\[
8 \times 7 \times 6 = 336.
\]
\underline{Il y a donc 336 façons de choisir et de classer ces 3 personnes.}

\item Pour classer 2 femmes et 1 homme, on doit d'abord choisir 2 femmes parmi les 4, puis 1 homme parmi les 4, et enfin les classer. Le nombre total de possibilités est donc :
\[
\dbinom{4}{2} \times \dbinom{4}{1} \times \fact{3} = 6 \times 4\times 6 = 144.
\]
\underline{Il y a donc 144 façons de former et classer ce groupe.}
\end{enumerate}

\medskip

\partie{C}

\begin{enumerate}
\item Le nombre de listes ordonnées de 3 personnes parmi les 8 invités est donné par :
\[
8^3 = 512.
\]
\underline{Il y a donc 512 possibilités.}

\item Le nombre de 3-uplets où les 3 personnes sont des femmes est donné par :
\[
4^3 = 64.
\]
La probabilité que les 3 personnes choisies soient des femmes est donc :
\[
\frac{64}{512}=\dfrac{1}{8}.
\]
\end{enumerate}

\partie{D}

On doit former une équipe de 4 personnes parmi les 8, avec au moins une femme. Le nombre total de combinaisons pour former une équipe de 4 personnes parmi 8 est :
\[
\dbinom{8}{4}=70.
\]
Le nombre de combinaisons ne contenant que des hommes (choisir 4 hommes parmi 4) est : 1.

Le nombre de façons de former une équipe avec au moins une femme est donc :
\[
70-1 = 69.
\]

\end{exocor}


%%% NEW 2025

\begin{exocor}{regroupement de personnes}[2]
Les habitants d'un village sont classés en trois catégories différentes, notées A, B et C. 

On constitue un groupe de 12 personnes prises au hasard sur un total de 30 personnes qui ont bien voulu se réunir. Dans le groupe de 30 personnes,
\begin{itemize}
\item 7 sont de la catégorie A,
\item 15 sont de la catégorie B,
\item 8 sont de la catégorie C.
\end{itemize} 

\begin{enumerate}
\item Combien de groupes de 12 personnes peut-on constituer parmi les 30 personnes qui se sont réunies?
\item Combien de groupes de 12 personnes peut-on former avec une seule personne de la catégorie A et cinq personnes de la catégorie C?
\end{enumerate}

\tcblower

\begin{enumerate}
\item \textit{Combien de groupes de 12 personnes peut-on constituer parmi les 30 personnes qui se sont réunies?}

\medskip

On doit constituer des groupes de 12 personnes \textit{parmi} les 30 présentes. L'ordre de ces personnes se compte pas et il n'y a pas de répétitions possibles. Il s'agit donc ici d'une combinaison (sur le même modèle que les mains d'une carte).

\medskip

Il y a donc $\dbinom{30}{12}=\numprint{86493225}$ groupes possibles.

\item \textit{Combien de groupes de 12 personnes peut-on former avec une seule personne de la catégorie A et cinq personnes de la catégorie C?}

\medskip

Nous devons choisir 1 personne (parmi les 7 de la catégorie A), puis 5 personnes (parmi les 8 de la catégorie C), puis 6 personnes (parmi les 15 de la catégorie B). 

Il y a donc:
\[
\dbinom{7}{1} \times \dbinom{8}{5} \times \dbinom{15}{6} = \numprint{1961960}\text{ possibilités}.
\]
\end{enumerate}
\end{exocor}

%%%



\corriges
