\input{../preambules/prebeam.tex}

%Pour le TITLEPAGE
\title{Chapitre 7: \\
Dénombrement}

\date{}


\begin{document}

\begin{frame}
	\titlepage
	
	\begin{savoirfaire}
	\item Calculer des probabilités à l'aide du dénombrement.
	\item Calculer avec des factorielles et des coefficients binomiaux
	\end{savoirfaire}
\end{frame}

\section{Loi uniforme}
\subsection{Cardinal d'un ensemble fini}
\begin{frame}
	\titre
	\soustitre
	\begin{histoire}
		Dénombrer un ensemble, c'est compter les éléments de cet ensemble. On trouve des traces de dénombrement dans l'antiquité. Mais c'est en étudiant les jeux de hasard et le calcul des probabilités que le dénombrement se développe avec des Français comme Pascal ou Pierre de Fermat. 
	\end{histoire}	
	\pause
	\begin{defi}{Cardinal d'un ensemble fini}
	\begin{itemize}
\item On dit que l\textquoteright{}ensemble E est \textbf{fini}
si le nombre de ses éléments est fini. 
 \item Si le nombre de ses éléments est égal à un certain entier $n$, $n$ est appelé  \textbf{cardinal de
}\textbf{$E$} noté \textbf{card(}\textbf{$E$}\textbf{)}
ou $|E|$ ou encore $\# E$.
\end{itemize} 
	\end{defi}
	\pause
	\begin{ex}{Cardinaux simples}
	$ card(\entier{1,n}) =  \quad , \qquad card(\emptyset) = \quad$.
	$ card(\entier{0,n}) =  \quad , \qquad card(\entier{p,n}) = \quad$.
	\end{ex}
	
\end{frame}

\begin{frame}
\begin{prop}{}
Soit A   un sous-ensemble fini de E. Alors A est un ensemble fini et  on sait de plus que
$card(A)\leq card(E)$.
Dans ce cas là, on sait par ailleurs que 
$$A = E \Longrightarrow \card(A) = \card(E).$$
\end{prop}
\pause
\remarque{On peut avoir card(A) = card(E) avec
$A\neq E$.}
\tableau{Donner deux ensembles ayant même cardinal mais qui
sont différents}
\end{frame}

\subsection{Loi de probabilité uniforme}
\begin{frame}
\soustitre
\pause
\begin{defi}{Loi uniforme}
Dans le cas où tous les évènements élémentaires ont la même probabilité, on dit qu'ils sont équiprobables, ou que la loi de probabilité $P$ est uniforme. Si $\Omega = \{ x_1, \ldots x_n \}$ alors la probabilité de chaque issue est 
\[ p = \dfrac{1}{\card(\Omega)} = \dfrac{1}{n} \]
\end{defi}

\begin{ex}{Dé à 6 faces}
La probabilité de tomber sur n'importe quelle face est $\frac{1}{6}$.
\end{ex}
\pause
\begin{prop}{Formule d'équiprobabilité}
Soit {$\left(\Omega,\:\partie{\Omega},\: P\right)$} un espace
probabilisé fini muni d'une loi uniforme, alors
\vspace{-8pt}
\[
\forall A \in \partie{\Omega}, \quad P(A) = \dfrac{\card(A)}{\card(\Omega)}
\]
\end{prop}
\tableau{\exercice}
\end{frame}

\subsection{Techniques de dénombrement générales}
\begin{frame}
\soustitre
\pause
\begin{prop}{Cardinal d'une union disjointe}
Soient A et B deux sous-ensembles disjoints d\textquoteright{}un ensemble
fini E.
Alors $A\cup B$ est un ensemble fini et 
\[card(A\cup B)=card(A)+card(B)
\]
\end{prop}
\tableau{\exercice}
\pause
\begin{prop}{}
Soient $A_{1}$,$A_{2}$, . . . ,$A_{n}$
n sous-ensembles de E deux à deux disjoints ( $\forall$(i, j){$\in$}$\left\{ 1,...,n\right\} ^{2}$,
$i\neq j\Rightarrow A_{i}\cap A_{j}= \emptyset $)
alors 
$$\card\left(\displaystyle \bigcup_{i=1}^{n}A_{i} \right)={\displaystyle \sum_{i=1}^{n}}\card(A_{i}).$$
\end{prop}
\tableau{\exercice}
\end{frame}

\begin{frame}
\begin{prop}{Crible de Poincaré}
Soient A, B et C des sous-ensembles d\textquoteright{}un ensemble
fini E.
\begin{itemize}
\item $\card(A\cup B)= \card(A)+ \card(B)- \card(A\cap B$).
\vspace{+5pt}
\item $ |A\cup B\cup C| = |A| + |B| + |C| - |A\cap B|- |A\cap C|- |B\cap C|+|A\cap B\cap C|$.
\end{itemize}
\end{prop}
\tableau{\exercice}
\end{frame}

\begin{frame}
\begin{theo}{}
Soit $A_1,\cdots,A_n$ une partition de $E$, alors pour tout $B \in \mathcal{P}(E)$,
\vspace{-5pt}
$$
\card(B)=\sum_{i=1}^n\card(B\cap A_i)
$$
\vspace{-5pt}
\end{theo}
\pause
\remarque{Dans le cas $n=2$, la partition de $E$ devient $A,\bar{A}$ et le résultat du théorème:
\vspace{-5pt}
$$
\card(B)
=\card(B\cap A)+\card(B\cap \bar{A})
$$}
\vspace{-25pt}
\tableau{\exercice}
\pause
\begin{prop}{Cardinal du complémentaire}
Soit A un sous-ensemble d\textquoteright{}un
ensemble fini E, alors :
\[
\card\left(\overline{A}\right)=\card(E) -\card(A)
\]
\end{prop}
\tableau{\exercice}
\end{frame}

\section{Méthodes de dénombrement}
\subsection{Utilisation d'un problème jouet}

\begin{frame}
\titre
\soustitre
\pause
\begin{metodo}{Problème jouet}
Dans toute la suite du cours, on va considérer l'expérience suivante. Dans un paquet, il y a $n$ cartes numérotées de $1$ à $n$. On tire alors $p$ cartes de différentes façons:
\begin{enumerate}
\item En s'intéressant ou non à l'ordre des cartes tirées.
\item Avec/Sans remise des cartes une fois tirées. 
\end{enumerate} 
\end{metodo}
\pause
On complétera alors le tableau suivant
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$p$ cartes tirées sur $n$& Avec ordre & Sans ordre \\
\hline
Avec Remise & & \\
\hline
Sans remise & & \\
\hline
\end{tabular}
\end{center}

\end{frame}

\subsection{Tirage avec ordre et remise}

\begin{frame}
\soustitre
\begin{defi}{p-listes}
Soit {E }un ensemble de cardinal{ n
}et{ p} un entier non nul.On appelle\textbf{ }\textbf{{p}}\textbf{-liste} d'éléments choisis parmi les {n }éléments de {E} tout élément de $E^{p}$ c'est à dire tout {p-}uplet de la forme ($e_{1},\: e_{2},...,\: e_{p}$)%
\end{defi}
\tableau{\exercice}
\pause
\begin{prop}{Cardinal du produit cartésien - Choix successifs.}
Soient A et B deux ensembles finis. Le cardinal
du produit cartésien $A\times B$ est :
\[
Card(A\times B)=Card(A)\times Card(B)
\]
Plus généralement, si $A_{1},...,A_{n}$ désignent {n} ensembles
finis, alors :
\[
Card(A_{1}\times...\times A_{n})=Card(A_{1})\times....\times Card(A_{n})
\]
\end{prop}
\tableau{\exercice}
\end{frame}

\begin{frame}
\remarque{L'ordre des éléments figurant dans la {p}-liste est important.
Ainsi deux {p}-listes contenant les mêmes éléments dans des ordres
différents sont différentes. Ex: $(2,3,4)\neq(3,2,4)$.}
\pause
\remarque{Une {p}-liste peut contenir plusieurs fois le même élément. Ex: $(2,3,1,2)$.}
\pause
\begin{theo}{Nombre de p-listes}
Si E est un ensemble de cardinal n alors le nombre de p-listes
d'éléments de E est égal $n^{p}$.%
\end{theo}
\pause
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$p$ cartes tirées sur $n$& Avec ordre & Sans ordre \\
\hline
Avec Remise & p-listes : $n^p$ & \\
\hline
Sans remise & & \\
\hline
\end{tabular}
\end{center}
\tableau{\exercice}
\end{frame}

\subsection{Tirage avec ordre et sans remise}
\begin{frame}
\soustitre
\pause
\begin{defi}{Permutations}
On considère un ensemble $E$ de cardinal $n$.
Une \textbf{ permutation de} $E$ est un réarrangement des éléments de $E$. C'est à dire l'écriture des éléments de $E$ dans un ordre différent.
\end{defi}
\pause
\begin{ex}{Permutations}
Soit $E = \{ a,b,c\}$. Les triplets $(a,b,c)$, $(a,c,b)$ $(b,c,a)$ sont des permutations de $E$.
\end{ex}
\pause
\begin{theo}{Permutations}
Soit E un ensemble de cardinal n.
Le nombre de permutations de E est égal à n! .%
\end{theo}
\tableau{\exercice}
\end{frame}

\begin{frame}
\begin{defi}{Arrangements}
On appelle\textbf{ arrangement de}\textbf{{ p }}\textbf{éléments
de}\textbf{{ E }}une{ p}-liste d'éléments \textbf{distincts}
de {E}.%
\end{defi}
\pause
\remarque{Dans ce cas, on a $0 \leq p \leq n$. On ne peut pas tirer plus de boules qu'il n'y en a.}
\pause
\begin{theo}{Nombres d'arrangements}
Soit E est un ensemble de cardinal n.
Le nombre d'arrangements de p éléments de E $(p \leq n)$
est égal à :
{$n(n-1)...(n-p+1)={\displaystyle \prod_{k=0}^{^{p-1}}}(n-k)$=$\dfrac{n!}{(n-p)!} = A_{n}^{p}$
.}
\end{theo}
\pause
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$p$ boules tirées sur $n$& Avec ordre & Sans ordre \\
\hline
Avec Remise & p-listes : $n^p$ & \\
\hline
Sans remise & Arrangements : $A_n^p$ & \\
\hline
\end{tabular}
\end{center}
\tableau{\exercice}
\end{frame}


\subsection{Tirage sans ordre et sans remise}
\begin{frame}
\soustitre
\pause
\begin{defi}{Combinaisons}
Soit {E} un ensemble de cardinal {n}.
On appelle\textbf{ combinaison de }\textbf{{p}}\textbf{ éléments
de}\textbf{{ E}} toute partie à $p$ éléments de {E}.%
\end{defi}
\pause
\begin{ex}{Combinaisons}
Soit $E = \{ a,b,c, d, e\}$. Les ensembles $\{a,b,c\}$, $\{e,c,b\}$ et $\{a \}$ sont des combinaisons de $E$.
\end{ex}
\pause
\remarque{Les éléments d'une combinaison de {p} éléments de{ E} sont
deux à deux distincts donc 0$\leq p\leq card(E)$.}
\pause
\remarque{Puisque l'on considère des parties, L'ordre des éléments d'une combinaison n'a pas d'importance : c'est ce qui différencie une combinaison d'un arrangement.}
\tableau{Déterminer le nombres de combinaisons possibles.}
\end{frame}

\begin{frame}
\begin{theo}{Nombre de combinaisons}
Soit E est un ensemble de cardinal $n$.
Le nombre de combinaison de $p$ éléments de $E$ ($p\leq n$)
est: 
$$C_n^p = \binom{n}{p}=\frac{A_n^p}{p!}=\frac{n(n-1)\cdots(n-p+1)}{p!}=\frac{n!}{p!(n-p)!}$$
Ces nombres sont appelés ''coefficients binomiaux''.%
\end{theo}
\pause
\begin{theo}{Combinaisons avec répétitions (pas au programme)}
Soit E est un ensemble de cardinal $n$. Le nombre de combinaisons avec répétitions de $p$ éléments de $E$, noté $\Gamma_n^p$ est égal à
$$\Gamma_n^p = \binom{n+p-1}{p}= \frac{(n+p-1)!}{p!(n-1)!}, $$
\vspace{-5pt}
\end{theo}
\pause
\vspace{-16pt}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$p$ boules tirées/$n$& Avec ordre & Sans ordre \\
\hline
Avec Remise & p-listes : $n^p$ & Combinaisons : $\Gamma_n^p$ \\
\hline
Sans remise & Arrangements : $A_n^p$ & Combinaisons : $C_n^p = \binom{n}{p}$ \\
\hline
\end{tabular}
\end{center}
\tableau{\exercice}
\end{frame}

\subsection{Propriétés des coefficients binomiaux.}
\begin{frame}
\soustitre
\begin{prop}{Calculs avec les coefficients binomiaux}
{$\forall n\in\mathbb{N}$ et $\forall$p $\in$ $\left\{ 1,\:...,\: n\right\} $,
}on a{ }:
\begin{qmulti}{2}
\item $\left(\begin{array}{c}
n\\
p
\end{array}\right)=\left(\begin{array}{c}
n\\
n-p
\end{array}\right)$ 
\item $\left(\begin{array}{c}
n\\
0
\end{array}\right)=\left(\begin{array}{c}
n\\
n
\end{array}\right)=1.$
\end{qmulti}
\pause
{$\forall n\in\mathbb{N}^{\star}$ et $\forall$p $\in$ $\left\{ 1,\:...,\: n-1\right\} $,}
on a{ }:
\begin{qmulti}{2}
\item $\left(\begin{array}{c}
n\\
1
\end{array}\right)=\left(\begin{array}{c}
n\\
n-1
\end{array}\right)=n$ 
\item $\left(\begin{array}{c}
n\\
p
\end{array}\right)=\dfrac{n}{p}\left(\begin{array}{c}
n-1\\
p-1
\end{array}\right).$
\end{qmulti}
\vspace{+3pt}
\end{prop}
\tableau{Preuve directe de la propriété et \exercice}
\pause
\begin{prop}{Triangle de Pascal}
Pour tout n et p deux entiers naturels
tels que $p\leqslant n$, on a :

\[
\left(\begin{array}{c}
n\\
p
\end{array}\right)+\left(\begin{array}{c}
n\\
p+1
\end{array}\right)=\left(\begin{array}{c}
n+1\\
p+1
\end{array}\right).
\]
\end{prop}
\end{frame}

\begin{frame}
\begin{theo}{Formule du binôme de Newton}
{Pour tout $(a,b)\in\mathbb{R}^{2}$ et $n\in\mathbb{N}$, on
a \[\qquad(a+b)^{n}={\displaystyle \sum_{k=0}^{n}\left(\begin{array}{c}
n\\
k
\end{array}\right)a^{k}b^{n-k}.}\]}%
\end{theo}
\pause
\begin{ex}{Exercice}
\begin{itemize}
\item Développez $(x+2)^2$, $(x+3)^3$
\item Calculez $\displaystyle \sum_{k=0}^n \binom{n}{k}$ et $\displaystyle \sum_{k=0}^n \binom{n}{k}(-1)^k $.
\end{itemize}
\end{ex}
\tableau{\exercice}

\pause
\begin{theo}{Cardinal des parties d'un ensemble}
Si $E$ est un ensemble à n éléments alors $card(\mathcal{P}(E))=2^{n}.$%
\end{theo}
\tableau{Pour la démonstration, voir l'exercice 19}
\end{frame}

\end{document}
