\chapter{Combinatoire\\et dénombrement}

\section{Principes de base}

\begin{exointro}{Lycée Saint-Joseph Loquidy, Nantes}
On considère trois ensembles: $E=\{1;2\}$, $F=\{1;2;3;4\}$ et $G=\{a;b;c\}$.

Quel est le nombre d'éléments de $(E\cup F)\times G$?
\end{exointro}

\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$ est un entier naturel.
\end{defin}

\subsection{Principe additif}
\enlargethispage*{2\baselineskip}
\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$, où $n$ et $m$ sont deux entiers naturels. Alors, le nombre de façons de prendre un élément dans $A$ \underline{ou} un élément dans $B$ est égal à $n+m$.

Cela se traduit ainsi:
\[
A \cap B \neq \varnothing \Rightarrow
\card(A \cup B) = \card A + \card B.
\]
\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$, où $n$ et $m$ sont deux entiers naturels.

Le nombre de façons de prendre un élément dans $A$ \underline{et} un élément dans $B$ est égal à $n \times m$. Cela se traduit ainsi:
\[
\card(A\times B)=\card A \times \card B.
\]
\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}

Les principe multiplicatif peut se représenter sous la forme d'un \textit{arbre des\linebreak possibilités}:\vspace*{-2em}
\begin{center}
\includegraphics{284_combinatoire-01-arbre}
\end{center}
On peut aussi considérer un tableau  à $n$ colonnes et $m$ lignes : il comporte $n \times m$ cellules.
\enlargethispage*{2\baselineskip}

\begin{solintro}
L'ensemble $E \cup F$ désigne les éléments qui sont dans $E$ \textit{ou} dans $F$: cet union comprend donc tous les éléments des deux ensembles. Or, $E$ est inclus dans $F$ donc $E \cup F = F$.

Ainsi, $(E\cup F) \times G$ représente donc le produit cartésien de $F$ et de $G$ et donc, d'après le principe multiplicatif:
\[
\card(F \times G) = \card(F) \times \card(G) = 4 \times 3 = 12.
\]
\end{solintro}

\section{Dénombrement}

\begin{exointro}{Lycée Saint-Joseph Loquidy, Nantes}
On considère l'ensemble:
\[
E=\{0;1;2;3;4;5;6;7;8;9\}.
\]
\begin{questions}
\item Calculer le nombre de 5-uplets d'éléments de $E$.
\item Combien de sous-ensembles de $E$ à 5 éléments existe-t-il ? 
\item Combien y a-t-il de triplets d'éléments distincts de $E$?
\end{questions}
\end{exointro}

\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{Remarque} 
par convention, $0!=1$.
\end{Remarque}

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

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

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

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

\begin{Exemple}un digicode à 4 chiffres est une 4-liste de l'ensemble $\{0;1;2;3;4;5;6;7;8;9\}$. La 4-liste (1;1;1;0) est différente de la 4-liste (0;1;1;1).
\end{Exemple}

\begin{prop}
Le nombre de $p$-listes prises 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\linebreak 4 chiffres.
\end{Exemple}

\subsection{Permutation}

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

Une \textit{permutation} de $E$ est un $n$-uplet 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{prop}
Il y a $n!$ permutations d'un ensemble à $n$ éléments.
\end{prop}

\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 une $p$-liste d'éléments 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}

\subsection{Combinaison}

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

Une \textit{combinaison} de $p$ éléments de $E$ est un ensemble (donc non ordonné) à \mbox{$p$ éléments} 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}

\Par

\begin{Exemple}$\dbinom{32}{5}=\dfrac{32\times31\times\cdots\times(32-5+1)}{5!}=\numprint{201376}$ donc il y a \numprint{201376} mains de 5 cartes possibles sur un jeu de 32 cartes.
\end{Exemple}

\Par

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

\Par

\begin{prop}[relation de Pascal]
\label{prop-triangle-pascal}
Pour tous entiers naturels $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}

\Par

De la propriété \ref{prop-triangle-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}.

\Par\Par

\begin{center}
\begin{tabular}{|>{\centering\arraybackslash}M{1cm}|*7{Zc|}}
\tabulartitle\hline
\diagbox[width=14mm,height=5mm]{$n$}{\raisebox{1mm}{$p$}} & 0 & 1 & 2 & 3  &4 & 5 & 6\\
\hline
0 & 1 & & & & & & \\
\hline
1 & 1 & 1 & & & & & \\
\hline
2 & 1 & 2 & 1 & & & & \\
\hline
3 & 1 & \multicolumn{2}{c|}{\cellcolor{LR}3 {\color{DR}$\xrightarrow{+}$} 3} & 1 & & & \\
\hline
4 & 1 & 4 &\cellcolor{LR} 6\psline[linecolor=DR]{->}(0.1,0.5)(0.1,0.1) & 4 & 1 & & \\
\hline
5 & 1 & 5 & 10 & 10 & 5 & 1 & \\
\hline
6 & 1 & 6 & 15 & 20 & 15 & 6 & 1\\
\hline
\end{tabular}
\end{center}

\newpage

\begin{aretenir}
\begin{center}
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|L|Zc|Zc|Z{m{3cm}}|}
\tabulartitle\hline
&  Ordre & Modèle &  Exemples\\
 \hline
 Permutation & \psline[linewidth=0.5pt](-0.39,1.12)(7.45,1.12) Oui & Tirage sans remise & Anagramme $^*$ \\
 \hline
 $p$-liste & Oui & Tirage avec remise  & Digicode\\
 \hline
 Arrangement $A_n^p$ & Oui & Tirage sans remise &Podium d'une course\\
 \hline
 Combinaison $\dbinom{n}{p}$  & Non & Tirage sans remise & Main dans un jeu de cartes\\
 \hline
\end{tabular}
\end{center}
\Par
$^*$ Permutation des lettres d'un mot formant un mot de sens différent.
\end{aretenir}

\Par

\begin{solintro}
$E=\{0;1;2;3;4;5;6;7;8;9\}$.
\begin{questions}
\item \textit{Calculer le nombre de 5-uplets d'éléments de $E$.}

Le nombre de 5-uplets d'éléments de $E$ est égal à $10^5=\numprint{100000}$ car $E$ contient 10 éléments.

\item \textit{Combien de sous-ensembles de $E$ à 5 éléments existe-t-il ?}

On nous demande ici le nombre de combinaisons à cinq éléments qu'il est possible de faire avec les éléments de $E$. En effet, l'ordre des éléments importe peu (contrairement aux arrangements) car l'ensemble $\{2;3;4;5;6\}$ est identique à l'ensemble $\{2;6;4;5;3\}$ (quand on parle d'ensemble, l'ordre ne compte pas).
\[
\dbinom{10}{5}=252.
\]
Il y a donc 252 sous-ensembles de $E$ à cinq éléments.

\item \textit{Combien y a-t-il de triplets d'éléments distincts de $E$?}

Un triplet, contrairement à un ensemble, est une liste \textit{ordonnée}. On cherche donc ici le nombre d'arrangements à trois éléments distincts de $E$.
\[
A_{10}^3 = \numprint{720}.
\]
Il y a donc \numprint{720} triplets d'éléments distincts de $E$.
\end{questions}
\end{solintro}