\chapterimage{compte}
\chaptertext{
Lors de l'étude des probabilités discrètes, il est primordial de compter
le   nombre    d'événements   réalisables.   On   met    donc   en   \og
correspondance\fg{}  des  éléments de  $\bbn$  avec des  événements:~on
\emph{dénombre}. 

Cela  peut  parfois  être  simple:~combien  y  a-t-il  d'issues  à  une
expérience de pile ou face?...

Mais on peut  souvent avoir besoin d'outils performants  que nous allons
présenter après quelques petits rappels.}

\chapter{Dénombrement}




\caml


\section{Rappels de théorie des ensembles}



\subsection{Ensembles finis}

Il est aisé  de comprendre intuitivement ce qu'est  un ensemble fini. En
voici une définition~:

\begin{definition}[Ensemble fini]
    On dit qu'un  ensemble E est fini si, et seulement  si, il existe un
    entier naturel $n$ et une bijection $\varphi$ de $\llbracket 1 , n\rrbracket$ sur E.
    \end{definition}
Cela signifie en  fait que chaque élément d'un ensemble  fini E porte un
numéro de dossard et qu'on connaît le nombre total de dossards~:~$n$. Ce
nombre jouant un rôle important, on lui donne un nom~:

\begin{definition}[Cardinal\index{cardinal} d'un ensemble fini]
    L'entier $n$ défini précédemment  est appelé \emph{cardinal de E} et
    noté Card(E) ou $\left|E\right|$.
    \end{definition}

Si on considère l'ensemble formé  des pages de cet ouvrage, il constitue
un ensemble fini~:~quel est son cardinal~?


Par     convention,     l'ensemble      vide     est     de     cardinal
nul~:~$\left|\emptyset\right|=0$.




\subsection{Parties d'un ensemble}


\begin{definition}[Parties d'un ensemble]
    Soit E  un   ensemble.   L'ensemble  formé   de  tous   les
    sous-ensembles de E  est appelé \emph{ensemble des parties  de E} et
    noté $\mathcal P(E)$.
    \end{definition}

Il faudra donc faire bien attention au moment d'utiliser les symboles $\in$
 et $\subseteq$. Ainsi~:

\[A\in\mathcal P(E) \lequiv A\subseteq E\]

Si $E_2=\bigl\{a,b\bigr\}$ alors $\mathcal P(E_2)=\Bigl\{\emptyset,\bigl\{a\bigr\},\bigl\{b\bigr\},\bigl\{a,b\bigr\}\Bigr\}$.

Nous  aurons  également   besoin  de  parler  des  éléments   de  E  qui
n'appartiennent pas à une de ses parties.


    \begin{definition}[Complémentaire d'une partie]
      Soit      A     une      partie     de      E.      On     appelle
      \textbf{complémentaire\index{complémentaire}}   de    A   dans   E
      l'ensemble des éléments de E  qui n'appartiennent pas à A. On note
      cet ensemble $\overline{A}_E$, $\complement_{E}A$ ou plus simplement $\overline{A}$
      quand il n'y a pas d'ambiguïté.
      \end{definition}
    

Par exemple, le complémentaire de  l'ensemble des filles dans une classe
est l'ensemble des garçons de cette classe.
La notation  permet de  faire le lien  avec la  négation d'une
  proposition:~la négatiion de \og $x\in A$\fg{} est \og $x\in\overline{A}$\fg{}...

\section{Une dose d'algèbre générale}

\subsection{Relation d'ordre\index{relation d'ordre}}

Soit A, B et C trois éléments de $\mathcal P(E)$.

Considérons la relation d'inclusion\index{d'inclusion} ($\subseteq$) qui relie deux éléments quelconques de $\mathcal P(E)$.

On obtient facilement que~:

\begin{itemize}
\item   $A\subseteq   A$~:~on   dit   que  la   relation   $\subseteq$   est
  \emph{réflexive\index{réflexive}}~;
\item $A\subseteq  B \wedge  B\subseteq A\imp A=B$~:~on  dit que  la relation
  $\subseteq$ est \emph{antisymétrique\index{antisymétrique}}~;
\item $A\subseteq B \wedge B\subseteq C\imp A\subseteq C$~:~on dit que la relation
  $\subseteq$ est \emph{transitive\index{transitive}}.
\end{itemize}
\begin{theoreme}[La relation d'ordre $\boldmath \subseteq\unboldmath$]
    Ces  trois propriétés  étant vérifiées,  on  dit que  $\subseteq$ est  une
\textbf{relation d'ordre} sur $\mathcal P(E)$.

    \end{theoreme}

Vous vérifierez que la relation  $\ie$ sur $\bbr$ a exactement les mêmes
propriétés~:~vous commencez  à entrevoir l'essence de  l'algèbre qui est
de dégager et d'étudier des structures les plus générales possibles afin
de simplifier l'étude de phénomènes qui paraissaient différents.


\subsection{Loi de composition interne\index{loi de composition interne}}


\begin{definition}[Réunion d'ensembles\index{réunion}]
    La réunion de  deux ensembles A et B notée  $A\cup B$ est l'ensemble
    des éléments appartenant à A \textbf{OU} B.
    \end{definition}
Le \og ou  \fg{} correspond bien sûr à  celui de la définition~\vref{ou},
c'est-à-dire qu'il est inclusif\index{inclusif}. 

\begin{itemize}
\item Comme $A\cup  B$ est encore  un élément de  $\mathcal P(E)$, on  dit que
$\cup$ est une \textbf{loi de composition interne}~;
\item comme $A\cup(B\cup  C)=(A\cup B)\cup C$, on dit  que la loi $\cup$
  est \textbf{associative}~;
\item comme $A\cup B=B\cup A$, on dit que la loi $\cup$
  est \textbf{commutative}~;
\item  comme  $A\cup  \emptyset=A$,  on  dit  que  $\emptyset$  est  une
  \textbf{élément neutre\index{élément neutre}} pour la loi $\cup$~;
\item comme $A\cup A=A$, on dit que la loi $\cup$ est \textbf{idempotente\index{idempotent}}.
\end{itemize}

On  peut  remarquer  que  ces propriétés  sont  vérifiées  par
  l'addition sur $\bbn$, l'élément neutre étant 0.


\begin{definition}[Intersection d'ensembles\index{intersection}]
    L'intersection de  deux ensembles A et B notée  $A\cap B$ est l'ensemble
    des éléments appartenant à A \textbf{ET} B.
    \end{definition}

%Le \og et \fg{} correspond à celui de la définition~\vref{et}.

Vous vérifierez que la loi $\cap$ a les mêmes propriétés que $\cup$ avec
cette fois comme élément neutre E.





\subsection{Lien avec les opérateurs logiques}


Comme souvent  en mathématiques,  on retrouve des  structures semblables
dans des domaines différents. 

Nous avons déjà découvert les liens entre $\cup$ et OU puis entre $\cap$
et ET.

On peut également faire le rapprochement entre l'implication des
propositions et  l'inclusion des  ensembles, \og vrai\fg{}  correspondant \og
$\in$\fg{}.


Ainsi, si  deux ensembles A  et B vérifient  $A\subseteq B$, alors  il est
impossible  de trouver  un élément  $x$ tel  que $x\in  A$  et $x\not\in
B$. Tous les autres cas sont possibles.

De même,  si $A\imp B$,  il est  impossible que A  soit vraie et  B soit
fausse. Toutes les autres propositions sont vraies.


On fait  le même rapprochement  entre l'équivalence des  propositions et
l'égalité des ensembles. Merveilleuses mathématiques...






\subsection{Partition\index{partition}}


On    a     souvent    besoin    de    découper     un    ensemble    en
tranches (souvenez-vous de votre cours de terminale sur les
  probabilités totales...). Voici une définition utile:

\begin{definition}[Partition d'un ensemble]
   La  famille  $(A_i)_{i\in\llbracket  1,n\rrbracket}$ de  parties  non
   vides d'un ensemble E  réalise une \textbf{partition} de cet ensemble
   si, et seulement si~:
\[\forall i\neq j, \ \ A_i\cap A_j=\emptyset \quad \land \quad \bigcup_{i=1}^nA_i=E\]
    \end{definition}
Par exemple, une partie A de  E et son complémentaire dans E réalise une
partition de E car $A\cap \overline{A}=\emptyset$ et $A\cup \overline{A}=E$.




\subsection{Produit cartésien\index{produit cartésien}}

\begin{definition}[Produit cartésien]
    Soit   $(A_i)_{i\in\llbracket  1,n\rrbracket}$   des   parties  d'un
    ensemble E.
Le produit  $\displaystyle\prod_{i=1}^nA_i=A_1\times A_2\times \cdots\times
A_n$  est  l'ensemble des  $n$-listes  $(x_1,x_2,\dots,x_n)$ telles  que
$x_1\in A_1$,...,$x_n\in A_n$.
    \end{definition}

Soit  $A=\bigl\{1,3,5,7,9\bigr\}$ et  $B=\bigl\{0,2,4,6,8\bigr\}$. Alors
$(1,0)$  est un  élément de  $A\times B$  et $(0,1)$  est un  élément de
$B\times  A$. {L'ordre des  ensembles dans  le produit  et donc
  des éléments dans les $n$-listes est important~!}



\section{Quelques résultats sur les cardinaux}


\subsection{Cardinal de $\mathcal P(E)$}
Soit $E_2=\bigl\{a,b\bigr\}$
et $E_3=\big\{a,b,c\big\}$. 
En fait,  $E_3=E_2\cup \bigl\{c\bigr\}$. Les parties de  $E_3$ sont donc
les parties de $E_2$ et ces mêmes parties auxquelles on adjoint c. 

En
effet,                                                          $\mathcal
P(E_3)=\Bigl\{\emptyset,\bigl\{a\bigr\},\bigl\{b\bigr\},\bigl\{a,b\bigr\},
\emptyset\cup                         \bigl\{c\bigr\},\bigl\{a\bigr\}\cup
\bigl\{c\bigr\},\bigl\{b\bigr\}\cup
\bigl\{c\bigr\},\bigl\{a,b\bigr\}\cup \bigl\{c\bigr\}\Bigr\}$.

Ainsi      $\left|\mathcal      P(E_3)\right|=2\times     \left|\mathcal
  P(E_2)\right|$.

Notons  de  manière générale  $E_n$  un  ensemble  à $n$  éléments  avec
$n\in\bbn$   et  $E_{n+1}=E_n\cup  \bigl\{\alpha\bigr\}$   avec  $\alpha
\not\in E_n$. On montre facilement que  $\left|\mathcal      P(E_{n+1})\right|=2\times     \left|\mathcal
  P(E_n)\right|$.  Or   $\mathcal  P(E_0)=\bigl\{\emptyset\bigr\}$  donc
$\left|\mathcal P(E_0)\right|=1$. 

une rapide récurrence permet donc de prouver que~:

\begin{theoreme}[Cardinal de $\boldmath \mathcal P(E)\unboldmath$]
    Si $\left|E\right|=n$ alors $\left|\mathcal P(E)\right|=2^n$
    \end{theoreme}


\subsection{Cardinal d'une partition}

Il est assez immédiat d'obtenir le résultat suivant~:

\begin{theoreme}[Cardinal d'une partition]\label{cardpart}
    Si la famille $(A_i)_{i\in\llbracket 1,n\rrbracket}$ de parties non
   vides d'un ensemble E  réalise une \textbf{partition} de cet ensemble
   alors~:

\[\left|E\right|=\sum_{i=1}^n \left|A_i\right|\]
    \end{theoreme}


{Pour compter  les élèves du  lycée, il suffit  de compter les  élèves de
chaque classe et d'additionner les résultats...}


\subsection{Cardinaux et inclusion}

\begin{theoreme}[]\label{cardinc}
    $\forall (A,B)\in\mathcal P(E)\times  \mathcal P(E),\ A\subseteq B\limp
    |A|\leqslant  |B|$
    \end{theoreme}


Pour  le  prouver,  il  suffit  d'utiliser  une  petite  ruse  (bientôt)
habituelle~:~A et $\overline{A}\cap B$  forment une partition de B donc,
d'après             le             théorème             \vref{cardpart},
$\left|A\right|+\left|\overline{A}\cap   B\right|=\left|B\right|$,  donc
$\left|A\right|\ie \left|B\right|$

{Cette   application  n'est   pas   une  équivalence~!   Prenez
  $A=\bigl\{1\bigr\}$ et $B=\bigl\{3 ; 4\bigr\}$}

\subsection{Cardinal d'un produit cartésien}





Voici un autre résultat qui sera bien utile en probabilités~:


\begin{theoreme}[Cardinal d'un produit cartésien]
     Soit   $(A_i)_{i\in\llbracket  1,n\rrbracket}$   des   parties  d'un
    ensemble E.  

$$\left|\displaystyle\prod_{i=1}^nA_i\right|=\displaystyle\prod_{i=1}^n\left|A_i\right|$$ 
    \end{theoreme}


En   effet,   pour   chaque    $n$-liste   $(x_1,...,x_n)$,   il   y   a
$\left|A_1\right|$ choix pour la première composante, $\left|A_2\right|$
choix pour la deuxième, etc.

\subsection{Formule du crible}


Nous n'en verrons qu'un cas particulier que vous devez déjà connaître~:

\begin{theoreme}[Formule du crible pour deux ensembles]\label{crible}
    $\forall  (A,B)\in\mathcal  P(E)\times  \mathcal P(E),\  \left|A\cup
      B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|$
    \end{theoreme}

Pour le  démontrer, nous allons former  une partition de  $A\cup B$ avec
$A\cap \overline{B}$, $\overline{A}\cap B$ et $A\cap B$.

Mais on peut également \og partitionner\fg{} A avec $A\cap \overline{B}$
et $A\cap B$ puis \og partitionner\fg{} B avec $B\cap \overline{A}$
et $B\cap A$.

On  obtient  donc  que $|A|=\left|A\cap  \overline{B}\right|+\left|A\cap
  B\right|$ puis que $|B|=\left|B\cap  \overline{A}\right|+\left|B\cap
  A\right|$.


On en déduit que $\left|A\right|+\left|B\right|=\left|A\cap  \overline{B}\right|+\left|B\cap  \overline{A}\right|+\left|A\cap
  B\right|+\left|B\cap
  A\right|$ et enfin que~: $$\left|A\right|+\left|B\right|-\left|A\cap B\right|=\left|A\cap  \overline{B}\right|+\left|B\cap  \overline{A}\right|+\left|A\cap
  B\right|=\left|A\cup B\right|$$




\section{Dénombrement}



\subsection{Nombre de permutations}


  \begin{definition}[Permutation]
    Soit  E  un ensemble.  Une  permutation  de  E est  une  application
    bijective  de E  sur  E. On  note  $\mathfrak{S}(E)$ l'ensemble  des
    permutations de E.
  \end{definition}



Généralement, on  note les permutations  sous forme d'une matrice  où la
première  ligne correspond aux  éléments de  E et  où la  deuxième ligne
correspond aux images des éléments de E.


Par exemple, les permutations de  $\bigl\{a,b,c\bigr\}$ sont:


$$
\begin{pmatrix}
  a&b&c\\
  a&b&c
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  a&c&b
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  b&a&c
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  b&c&a
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  c&a&b
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  c&b&a
\end{pmatrix}
$$

On peut même se contenter d'écrire $(a,b,c)$,
$(a,c,b)$, $(b,a,c)$,  $(b,c,a)$, $(c,a,b)$,  $(c,b,a)$ si l'on  est sûr
que la première ligne est toujours $(a,b,c)$. 



\begin{theoreme}[Nombre de permutations]
    Il y a $n!$ permutations d'un ensemble de $n$ éléments.
    \end{theoreme}




La démonstration  s'effectue par  récurrence. Il y  a bien sûr  1! façon
de permuter 1 élément.

On peut  donc supposer qu'il existe au  moins un entier $k$  tel qu'il y
ait $k!$ permutations d'un ensemble à $k$ éléments.

Considérons un ensemble à $k+1$ éléments. On en choisit 1~:~il y a $k+1$
choix possibles. Ensuite, il  s'agit d'ordonner les $k$ éléments restant
ce qui laisse $k!$ possibilités.

Il y a donc finalement $(k+1)\times k!=(k+1)!$ permutations au total.


On retrouve  dans l'exemple précédent  qu'il y a $3!=6$  permutations de
$\bigl\{a,b,c\bigr\}$.


{On conviendra que $0!=1$.}

On  a déjà rencontré  les permutations  lors de  notre découverte  de la
cryptographie.  Elles  jouent  également  un  rôle  important  dans  les
algorithmes  de  tri par  exemple  et  aussi  dans certains  algorithmes
concernant les  graphes que vous  étudierez en deuxième année,  dans les
mélanges  de cartes,  dans l'étude  du  Rubik's cube,  et bien  d'autres
domaines encore...


\begin{remarque}[Formule de \textsc{Stirling}]
  Pour $n$ \og grand\fg{}, on peut estimer que:

  $$n! \displaystyle\underset{+\infty}\sim \sqrt{2\pi n}\left(\frac{n}{\mathrm{e}}\right)^n$$



\end{remarque}

\subsection{Nombre d'applications injectives - arrangements sans répétitions}



Une source veut envoyer à chacun de ses cinq clients 
un fichier différent parmi les vingt-six situés dans un certain répertoire.

Combien de possibilités a la source pour envoyer un fichier à chacun des
26 clients?

On peut modéliser cette situation: il s'agit de compter les applications injectives
(pourquoi \og injectives\fg{}?)
de l'ensemble E des clients vers l'ensemble F des fichiers.  Il ne peut y
avoir  répétition donc  il y  a  26 choix  de fichiers  pour le  premier
client,  25 pour  le deuxième,  etc.   ce qui  donne $26\times  25\times
24\times 22\times 21$ possibilités.

On peut généraliser.

\begin{definition}[Arrangement sans répétition]
 Une  application injective  d'un ensemble  E  de cardinal  $p$ dans  un
 ensemble F de cardinal $n$ (avec $p \leqslant n$) est appelée un arrangement sans répétition
 de $p$ parmi $n$.
\end{definition}


Un exemple fameux est la  recherche de tiercés dans l'ordre (sans ex-\ae
quo...): pourquoi?




Nous pouvons formuler cette propriété plus synthétiquement. En
effet
$$A_n^p=n(n-1)(n-2)\cdots(n-p+1)\times
\frac{(n-p)(n-p-1)(n-p-2)\times\cdots\times 2\times
1}{(n-p)(n-p-1)(n-p-2)\times\cdots\times 2\times
1}=\frac{n!}{(n-p)!}$$ d'où


\begin{theoreme}[Nombre d'arrangements]
  Le nombre d'arrangements sans répétition de $p$ parmi $n$ est 
$$A_n^p =n(n-1)(n-2)\cdots(n-p+1)= \frac{n!}{(n-p)!}$$
\end{theoreme}

Preuve?



\subsection{Combinaisons sans répétition}


Il n'y a pas assez de gagnants au loto. Les règles en sont donc
modifiées. Il s'agit maintenant de trouver 3 numéros parmi 5.
Combien y a-t-il de grilles (combinaisons) possibles~?

Par exemple, on pourrait dire que j'ai cinq manières de choisir le
premier numéro, quatre choix pour le deuxième et trois choix pour
le troisième, donc il y a $5\times 4\times 3$ grilles différentes
mais  dans  ce cas,  je  compte des  3-listes  ordonnées  alors que  les
3-listes  $(1,2,3)$  et $(3,2,1)$  correspondent  à  la  même grille  ou
combinaison $\bigl\{1,2,3\bigr\}$.  

 


Posons une petite définition pour clarifier les débats. Donnons en
fait un nom à une grille du loto, c'est à dire à un sous-ensemble
(une partie) contenant $p$ éléments d'un plus grand ensemble
contenant $n$ éléments.


\begin{definition}[Combinaison sans répétition]
    Soit $n$ et $p$ deux entiers naturels et $E$ un ensemble contenant $n$ éléments. Un sous-ensemble de $E$ contenant $p$
éléments est appelé  une \textbf{combinaison} de $p$ éléments  de $E$ ou
encore une {$\boldmath p\unboldmath$}\textbf{-combinaison} d'éléments de
\unboldmath${E}$.
    \end{definition}

Or ce qui nous intéresse, c'est le nombre de ces combinaisons,
donc introduisons une notation:


\begin{definition}[Nombre de combinaisons sans répétitions]
     Le nombre de $p$-combinaisons d'un ensemble E contenant $n$ éléments
     est noté ${E\choose p}$ ou encore $C_{|E|}^p=C_n^p$
    \end{definition}

Revenons à notre mini-loto. Considérons une grille quelconque
(i.e. une 3-combinaison de l'ensemble des 5 numéros)~: par
exemple $\{2,4,5\}$. Nous  avons vu dans un paragraphe précédent
qu'il y a $3!$ facons d'ordonner ces nombres. Finalement, il y a
$C_5^3  \times  3!$ suites  de  3  nombres  ordonnées: c'est  le  nombre
d'arrangements de $p$ parmi $n$. Or nous en
avons comptées $5\times 4\times 3$ tout à l'heure. Nous en
déduisons finalement que
$$C_5^3=\frac{A_5^3}{3!}=\frac{5\times 4\times 3}{3!}$$

Il est alors possible de généraliser la formule suivante:


\begin{theoreme}[]
     $$C_n^p=\frac{A_n^p}{p!}=\frac{n\big(n-1\big)\big(n-2\big)\cdots\big(n-(p-1)\big)}{p!}=\frac{n!}{p!(n-p)!}$$
    \end{theoreme}

Preuve?




\section{Triangle de Pascal - Binôme de Newton}

%\subsection{Raisonnement calculatoire}

À l'aide des formules précédentes, on prouve facilement (faites-le~!) le
résultat suivant~:


\begin{theoreme}[]
    $$C_n^p=C_{n}^{n-p}$$
    \end{theoreme}





On établit ensuite, toujours par le calcul, la relation suivante, dite \textbf{Relation de Pascal} même si les mathématiciens chinois l'avaient
mise en évidence avant lui~:


\begin{theoreme}[Relation de \textsc{Pascal}]\label{fpascal}
     $$C_{n}^{p}=C_{n-1}^{p}+C_{n-1}^{p-1}$$
    \end{theoreme}


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{4.2cm}
%\begin{figure}
  \includegraphics[width=3cm]{pascal500}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Il est  possible de démontrer  cette formule à l'aide  d'un raisonnement
ensembliste~:~pour former  des groupes de $p$ éléments  dans un ensemble
en contenant $n$, on distingue un élément $n_0$ quelconque~:
\begin{itemize}
\item soit le groupe le contient et alors il y a $C_{n-1}^{p-1}$
  choix des $p-1$ éléments distincts de $n_0$ parmi les $n-1$ restant~;
\item soit  le groupe  ne le contient  pas et  il faut donc  choisir $p$
  éléments parmi  les $n-1$  éléments distincts de  $n_0$~:~il y  a donc
  cette fois $C_{n-1}^{p}$.
\end{itemize}


Cette   relation  permet   de  démontrer   la  formule   du   binôme  de
Newton (que nous admettrons):

\begin{theoreme}[Formule du binôme]
 Soit $\bba$ un anneau commutatif. Dans $\bba[X]$, pour tout entier naturel non nul $n$:

$$(1+X)^n=\displaystyle\sum_{k=0}^{n}C_n^kX^k$$

et plus généralement:

$$\forall (a,b)\in\bba^2,\quad (a+b)^n=\displaystyle\sum_{k=0}^{n}C_n^ka^kb^{n-k}$$
\end{theoreme}



%%%%%%%%%%%%%%%%%%%%%
%
%
%              E X E R C I C E S
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vfill

\eject

\section{EXERCICES}


%%%%%%%%%%%%%%%%%%%%%

%%% new exos

%%%%


\begin{exercice}[Pour]
Que vaut $k$ à la fin?
\begin{multicols}{2}
  \begin{algo}
    \STATE{k\recoit{}0}
\FOR{$i_1$}{1}{$n_1$}
\FOR{$i_2$}{1}{$n_2$}
\STATE{\hspace{1.5cm}$\vdots$}
\FOR{$i_p$}{1}{$n_p$}
\STATE{k\recoit{}k+1}
\ENDFOR
\ENDFOR
\ENDFOR
\RETURN{k}
  \end{algo}

 \begin{algo}
    \STATE{k\recoit{}0}
\FOR{$i_1$}{1}{$n_1$}
\STATE{k\recoit{}k+1}
\ENDFOR
\FOR{$i_2$}{1}{$n_2$}
\STATE{k\recoit{}k+1}
\ENDFOR
\STATE{\hspace{1.5cm}$\vdots$}
\FOR{$i_p$}{1}{$n_p$}
\STATE{k\recoit{}k+1}
\ENDFOR
\RETURN{k}
  \end{algo}


\end{multicols}


\begin{multicols}{2}


 \begin{algo}
    \STATE{k\recoit{}0}
\FOR{$i_1$}{1}{$n_1$}
\STATE{k\recoit{}k+1}
\FOR{$i_2$}{1}{$n_2$}
\STATE{k\recoit{}k+1}
\STATE{\hspace{1.5cm}$\vdots$}
\FOR{$i_p$}{1}{$n_p$}
\STATE{k\recoit{}k+1}
\ENDFOR
\ENDFOR
\ENDFOR
\RETURN{k}
  \end{algo}

 \begin{algo}
    \STATE{k\recoit{}0}
\FOR{$x$}{1}{$100$}
\FOR{$y$}{1}{$x$}
\FOR{$z$}{1}{$y$}
\FOR{$t$}{1}{$z$}
\STATE{k\recoit{}k+1}
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
\RETURN{k}
  \end{algo}



\end{multicols}
\end{exercice}



\begin{exercice}[Chaînes]
  Combien y  a-t-il d'octets  commençant par 1  ou se terminant  par 00?
  Combien y en a-t-il ne contenant pas deux 1 consécutifs?
Combien y en a-t-il qui contiennent la chaîne 000 ou la chaîne 111?
\end{exercice}


\begin{exercice}[Principe des tiroirs]
 Si on a $n+1$ ou plus chaussettes  à ranger dans $n$ tiroirs, il y a au
 moins  un tiroir qui  en contient  2 ou  plus. Cette  affirmation assez
 simple est aussi appelé \textit{Principe de \textsc{Dirichlet}} ou même
 \textit{pigeon hole principle} par les anglo-saxons.

Démontrez le \textit{principe des tiroirs généralisé}: si on a $n$
 chaussettes  à ranger dans  $p$ tiroirs,  alors il  existe au  moins un
 tiroir contenant au moins $\left\lceil \frac{n}{p}\right\rceil$
 chaussettes.
Vous pourrez raisonner par l'absurde


\end{exercice}


\begin{exercice}[Téléphone]

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{telephone}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
On suppose que les numéros  de téléphone sont de la forme 0Z-YX-XX-XX-XX
avec X un nombre entier entre 0 et 9, Y un nombre entier entre 2 et 9 et
Z un entier entre 1 et 9.

En France, il  y a environ 40 millions d'abonnements  à un \og fixe\fg{}
et  69 millions  à un  \og mobile\fg{}  (données du  quatrième trimestre
2011).

Est-on tranquille? 

Supposons qu'en Syldavie, il y ait 109 millions d'abonnés à un téléphone fixe et que
le Y soit fixé par opérateur et qu'il n'y ait que deux opérateurs. De
combien de zones a-t-on besoin? 
\end{exercice}


\begin{exercice}[Câbles]
Il y a 1000 ordinateurs et  50 imprimantes. Combien faut-il au minimum de
câbles pour que 50 ordinateurs  pris au hasard puissent, à tout moment,
accéder chacun à une imprimante différente?
\end{exercice}

\begin{exercice}[Nombre d'applications]
  Combien y a-t-il d'applications d'un  ensemble de cardinal $n$ vers un
  ensemble de cardinal $p$?
\end{exercice}


\begin{exercice}[Barbie]

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{chador}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.4cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
  Un  étudiant de l'\textsc{Iut}  d'informatique de  Klow en  Syldavie a
  reçu pour Noël sept Barbie et sept séries de dix robes de couleurs différentes.
Il habille chaque Barbie d'une de ces robes.
\begin{enumerate}
\item Combien y a-t-il d'habillages possibles selon la couleur?
\item Combien y  a-t-il d'habillages de sorte que  chaque Barbie ait une
      robe de couleur différente des autres?
\item Combien  y a-t-il  d'habillages de sorte  qu'au moins  deux Barbie
      aient une robe de la même couleur?
\item Combien  y a-t-il  d'habillages de sorte  qu'exactement  deux Barbie
      aient une robe de la même couleur?

\end{enumerate}
\end{exercice}


\begin{exercice}[Jus]
  Lors de la soirée d'intégration de l'\textsc{Iut} de Klow, 9 étudiants
  ont bu un  verre d'eau, 25 un verre  de jus de tomate, 14  un verre de
  jus de betterave, 7 un verre de  jus de tomate et un verre d'eau, 4 un
  verre d'eau  et un verre de  jus de betterave,  10 un verre de  jus de
  betterave  et  un  verre  de  jus  de  tomate.  Les  étudiants  d'Info
  s'occupaient des boissons  et ceux de GEA des  entrées or ces derniers
  ont  perdu  leur liste  et  ne  savant  plus combien  d'étudiants  ont
  participé à la soirée.  Les étudiants d'Info, connaissant les
  statistiques sur les  consommations de boissons, pourront-ils corriger
  la gaffe  des GEA  sachant également  que lors de  la valse,  tous les
  participants dansaient en couple ?
\end{exercice}


\begin{exercice}[k-uplets]
   Soit $E$ un ensemble fini non vide de cardinal $n$.
\begin{itemize}
\item[a)] Combien y-a-t-il de parties de $E$ formées de $k$ éléments?
 \item[b)] Combien y-a-t-il de $k$-uplets d'éléments de $E$?
  \item[c)]  Combien  y-a-t-il  de  $k$-uplets d'éléments  deux  à  deux
distincts de $E$?
   \item[d)]  Combien  y-a-t-il de  $k$-uplets  d'éléments  deux à  deux
distincts de  $E$, tel que  le premier élément  est le plus petit  et le
dernier élément est le plus grand?
\item[e)] Combien y-a-t-il de $k$-uplets d'éléments de $E$ ordonnés dans
l'ordre strictement croissant?
\end{itemize} 
\end{exercice}


\begin{exercice}[Arrangements]
  Comment modéliser le tiercé  brillamment organisé par le \textsc{Pmu}?
  (Qui est E? Qui est F? Quelle est l'application de E dans F?)
Combien y a-t-il  de tiercés possibles (sans ex-\ae  quo) dans
une course de 19 partants?

Modélisez  la recherche  du nombre  d'arrangements  de $p$  parmi $n$  à
l'aide d'un tirage de boules dans une urne.
\end{exercice}



\begin{exercice}[L'âge du capitaine]
  
 Le capitaine  des pompiers  de New-York est  marié et a  quatre enfants
 dont un mange un yaourt aux fruits tous les matins. Il ne fume pas, aime
 regarder des films de gladiateurs et réside \`a l'angle de la
 1\up{ère}
avenue et de  la 33\up{ème} rue. La caserne se trouve  \`a l'angle de la
9\up{ème} avenue et de la 40\up{ème} rue. Il s'y rend tous les jours \`a 
pied en sifflant \og $\mathfrak{O\ du\ schöner\ Westerwald}$\fg{} et sans perdre de temps (i.e. dans le sens des numéros
croissants aussi bien pour les rues que pour les avenues). Sachant qu'il
a commencé \`a travailler le jour  de ses 18 ans, et sachant qu'il n'est
jamais passé deux  fois par le m\^eme chemin,  qu'il boîte légèrement de
la  jambe  droite  après  avoir  participé au  championnat  d'Écosse  de
lancement d'enclume, qu'il est sourd  de l'oreille gauche depuis qu'il a
plongé dans  un lac gelé pour sauver  son petit frère John  qui était en
train de  se noyer après  que la glace  sur laquelle il  patinait craqua,
quel est l'\^age (maximum) du capitaine ?


\end{exercice}



\begin{exercice}[\textsc{Stirling} strikes back]
  Donnez un équivalent de $C_{2n}^n$ quand $n$ tend vers l'infini.
\end{exercice}



\begin{exercice}[Mélange de cartes]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{melange}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.6cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


On  dispose d'un  jeu de  52 cartes  et on  le mélange  en \textit{queue
d'aronde}:
% %\begin{figure}
% \begin{center}
%   \includegraphics[width=5cm]{melange}
% \end{center}
% %\end{figure}
on divise le jeu en deux parties de 26 cartes et on intercale les cartes
de  la moitié  gauche dans  la moitié  droite sans  modifier  l'ordre de
chaque partie bien sûr.
Est-ce que  quatre mélanges en  queue d'aronde successifs  permettent de
fournir un ordre aléatoire des cartes? 

Il  faudrait préciser d'abord  cette notion:  combien y  a-t-il d'ordres
possibles des cartes?

Existe-t-il  alors des  ordres qui  ne pourront  être obtenus  par notre
succession de mélanges?
i 
Pour répondre à cette question,  il faudrait calculer le nombre d'ordres
qu'on peut  obtenir par la succession de  quatre mélanges...Imaginez que
vous disposiez de 26 cartes bleues  et 26 rouges. Vous les mélangez avec
la  méthode  de  la  queue  d'aronde: pouvez-vous  reconstituer  le  jeu
initial? Combien y a-t-il alors d'ordres possibles après le premier mélange?
\end{exercice}





























\begin{exercice}[Binôme]
  Soit E un ensemble  de cardinal $n$.  Si on remplace $a$  et $b$ par 1
  dans la formule du binôme, quel résultat 
  classique  retrouve-t-on? 
\end{exercice}


\begin{exercice}[Bibosses]
\begin{enumerate}
\item  En utilisant  la  relation de  \textsc{Pascal}, déterminez  une
  fonction \textsc{CaML} récursive de signature:
  \begin{lstlisting}
val binom1 : int -> int -> int = <fun>
  \end{lstlisting}
telle que \lstinline+binom1 n p+ calcule $C_n^p$.

On pourra alors  afficher le triangle de \textsc{Pascal}  à l'aide de la
fonction suivante:

\begin{lstlisting}[caption={}]
let triangle1 n =
for i = 0 to n do
  for j = 0 to i do
    print_int (binom1 i j);
    print_string " "
  done;
  print_newline ()
done;;
\end{lstlisting}
\item Calculez  $C_{30}^{10}$....mmmmmmm....c'est un  peu long.  On va
  essayer de rendre  notre récursion terminale en  utilisant une autre
  relation.   Déterminez  pour   cela   le  rationnel   $x$  tel   que
  $C_n^k=xC_{n}^{k-1}$   puis   déterminez  une   fonction   récursive
  terminale beaucoup plus
  rapide que celle mise au point dans la première question.



\item Une autre
      idée  est  d'utiliser un  tableau  a priori  rempli  de  0. On  va
      remplacer  certaines  cellules en  place  en  utilisant encore  la
      relation de \textsc{Pascal}.

      Avec notre chameau, on utilise la fonction \lstinline+Array.make_matrix n m+
      qui  construit une  matrice de  taille  $n\times m$.  On accède  à
      l'élément  situé  sur  la  ligne   $i$  et  la  colonne  $j$  avec
      \lstinline+t.(i).(j)+ si on a nommé \lstinline+t+ la matrice.

      On rappelle qu'on peut substituer la valeur initiale de la cellule
      $t_{ij}$ par la valeur $v$ en place à l'aide de la commande:

      \begin{lstlisting}[caption={}]
t.(i).(j) <- v
      \end{lstlisting}

On créera donc une fonction \lstinline+triangle2 n+ de signature:

\begin{lstlisting}[caption={}]
val triangle2 : int -> int array array = <fun>
\end{lstlisting}

puis une fonction \lstinline+binom_b n p+:

\begin{lstlisting}[caption={}]
let binom_b n p =
  let b = triangle2 n in
  b.(n).(p);;
\end{lstlisting}

Calculez  alors  $C_{30}^{10}$  avec  cette  nouvelle  fonction.
\item On voudrait donc comparer  la complexité en temps de ces fonctions
       en  prenant comme  unité une  addition de  coefficients binomiaux
       (on négligera les décrémentations d'indices). Faites-le!...
\item  Une petite  touche  artistique à  présent...Dans  le triangle  de
      \textsc{Pascal}, on  va remplacer  les coefficients pairs  par une
      espace et les impairs par une étoile. 

Créez  une  fonction  \lstinline+triangle4 : int -> unit = <fun>+  à  cet
effet. Que donne \lstinline+triangle4 n+ avec \lstinline+n+ égal successivement à
31, 63, 127, 255? 
\end{enumerate}
\end{exercice}













\begin{exercice}[Formules binomiales]
On voudrait calculer $\displaystyle\sum_{k=0}^{n}\left(C_n^k\right)^2$ à
l'aide du calcul d'un seul  coefficient binomial (i.e. déterminer $i$ et
$j$ tels que la somme précédente soit égale à $C_i^j$).

Plusieurs méthodes existent bien sûr.

Une  consiste à  avoir  un raisonnement  ensembliste  similaire à  celui
utilisé pour prouver la relation de \textsc{Pascal}.

Vous  déterminerez  d'abord  le  lien  entre  $\left(C_n^k\right)^2$  et
$C_n^kC_n^{n-k}$  puis vous  ferez le  lien entre  notre problème  et la
situation suivante: on  a $n$ filles et $n$  garçons; combien de groupes
de $n$ étudiants peut-on faire?...

\medskip

Une autre idée consiste à \og penser polynôme\fg{}:

$$(1+X)^n(1+X)^n=(1+X)^{2n}$$

Des idées?...
\end{exercice}

\begin{exercice}[Suissesses multinomiales]
Combien existe-il d'anagrammes au mot \og suissesses\fg{}? 


On définit un nouveau type de coefficient:

\begin{definition}[Coefficient multinomial]
Soit   $k_1$,   $k_2$,...,$k_p$    des   entiers   naturels   tels   que
$\displaystyle\sum_{i=1}^{p}k_i=n$. On note alors:

$$C_n^{k_1,k_2,...,k_p}=\frac{n!}{k_1!k_2!\cdots k_p!}$$
\end{definition}


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{heidi}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

Quel est le coefficient multinomial égal à $C_n^p$?

Comment interpréter ces coefficients en termes combinatoires?

Quel est le rapport avec les suissesses?
  

Il existe un pendant multinomial à la formule du binôme:

\begin{theoreme}[Formule du multinôme]
$$(x_1+x_2+\cdots+x_p)^n=\displaystyle\sum_{k_1+k_2+\cdots+k_p=n}
C_n^{k_1,k_2,...,k_p}x_1^{k_1}x_2^{k_2}\cdots x_p^{k_p}$$
\end{theoreme}

Par exemple, quel est le coefficient de $x^2y^3z^4$ dans $(x+y+z)^8$?
\end{exercice}


\begin{exercice}[Somme d'entiers]
  Prouvez la formule:
$C_{n+1}^{p+1}=\displaystyle\sum_{i=0}^{n-p}C_{p+i}^p$
Déduisez-en                               $\displaystyle\sum_{k=1}^{n}k$,
$\displaystyle\sum_{k=2}^{n}k(k-1)$, $\displaystyle\sum_{k=1}^{n}k^2$, $\displaystyle\sum_{k=1}^{n}k^3$.
\end{exercice}




\begin{exercice}[Encore une formule binomiale]
  

On considère $n$ boules num\'erot\'ees de 1 à n.

\begin{enumerate} 
\item Soit  $k$ un  entier v\'erifiant $p  \leqslant k \leqslant  n$. On
  tire simultanément $p$ boules de l'urne. Combien y a-t-il de
 tirages dont le plus grand num\'ero est $k$ ?

\item En d\'eduire une expression de $\sum\limits_{k=p}^{n}C_{k- 1}^{p-1}$   sous forme d'un unique coefficient binomial.

\end{enumerate}



\end{exercice}











\begin{exercice}[Dénombrement avec OCaml]

Nous allons construire quelques outils  fonctionnels pour nous aider à
résoudre certains problèmes de dénombrement et plus tard à simuler
certaines expériences aléatoires.

Pour cela, nous allons reprendre la structure de peigne vue en début
d'année pour modéliser les ensembles:

\begin{lstlisting}
type 'a ens =
  | Vide 
  | Ens of ('a * 'a ens);;
\end{lstlisting}
  

Il  va  s'agir dans  un  premier  temps  de créer  quelques  fonctions
terminales utiles pour la suite.  La plupart du temps, nous filtrerons
les ensembles par motifs. 

Voici par exemple une fonction qui extrait un élément du peigne:

\begin{lstlisting}
let tete = function
  |Vide     -> raise Ensemble_vide
  |Ens(t,q) -> t;;
\end{lstlisting}

\begin{enumerate}
\item   Créez   une   fonction  récursive   terminale   de   signature
  \lstinline+'a -> 'a ens -> bool = <fun>+ qui teste l'appartenance d'un élément à un
  ensemble:
\begin{lstlisting}
let rec appartient = fun el ensemble -> ...
\end{lstlisting}

\item On peut simplement rajouter un élément à un ensemble:

\begin{lstlisting}
let colle = fun el ens -> Ens(el,ens);;
\end{lstlisting}

Créez une  fonction \lstinline+ajoute = fun  el ens+ qui fait  la même
chose mais  n'ajoute l'élément  que s'il n'est  pas déjà  présent dans
l'ensemble.

\item Créez deux fonctions récursives terminales qui réalisent l'union
  de  deux   ensembles.  L'une  utilisera   \lstinline+colle+  l'autre
  \lstinline+ajoute+: pourquoi distinguer ces deux fonctions?

\item  Créez  une  fonction  \lstinline+applique  =  fun  f  ens+  qui
  appliquera la  fonction $f$  à tous les  éléments de  l'ensemble. Sa
  signature sera \lstinline+('a -> 'b) -> 'a ens -> 'b ens = <fun>+. 

\item Créez  une fonction \lstinline+plie =  fun f e0 ens+  qui va \og
  plier\fg{} l'ensemble  selon le modèle de  \lstinline+fold_left+. La
  signature sera \lstinline+('a -> 'b -> 'a) -> 'a -> 'b ens -> 'a = <fun>+. 

\item    En   utilisant    \lstinline+plie+,   créez    une   fonction
  \lstinline+cardinal  =  fun  ens+   qui  calcule  le  cardinal  d'un
  ensemble. On  ne tiendra pas  compte des éventuels doublons.  Pour y
  remédier si besoin, créez à part une fonction \lstinline+reduit = fun ens+ 
qui renvoie l'ensemble donné en argument débarrassé de ses doublons.



\item Que fait la fonction suivante:

\begin{lstlisting}
let rec mystere  = fun ens n ->
  if n = 0 then
      Ens(Vide,Vide)
  else 
    match ens with
      Vide    ->  Vide 
    |Ens(t,q) ->  union_colle (applique (colle t) (mystere q (n-1)))  (mystere q n);;
\end{lstlisting}
 
Cette fonction nous sera très utile...

\item Il sera plus pratique de lire ou d'écrire des ensembles à partir
  de la liste de leurs éléments.

Créez alors une fonctions \lstinline+liste_el  = fun ens+ de signature
\lstinline+'a ens -> 'a list = <fun>+ qui renvoie
la liste des éléments d'un ensemble sans doublons.

Créez de  même une  fonction \lstinline+ens_of_list  = fun  liste+ qui
crée l'ensemble associé à la liste donnée en argument.


\item  Créez   une  fonction  applatit  qui   trensforme  un  ensemble
  d'ensembles d'éléments de type 'a  en un ensemble d'éléments de type
  'a,  comme  le fait  \lstinline+List.flatten+  pour  les listes.  La
  signature sera donc \lstinline+'a ens ens -> 'a ens = <fun>+. 

\item Créez une fonction qui filtre un ensembe selon un prédicat comme
  le fait  \lstinline+List.filter+ pour les  listes et aura  donc pour
  signature \lstinline+('a -> bool) -> 'a ens -> 'a ens = <fun>+. 





\item  Créez une  fonction \lstinline+partition  = fun  pred ens+  qui
  renvoie un couple d'ensembles: le premier élément du couple contient les éléments qui
  vérifient le prédicat et le second les autres. 

  La signature sera donc \lstinline+('a -> bool) -> 'a ens -> 'a ens * 'a ens = <fun>+. 


\item  Créez une  fonction \lstinline+count  = fun  ens+ de  signature
  \lstinline+'a  ens ->  ('a  *  int) list  =  <fun>+  qui compte  les
  occurences de chaque élément d'un ensemble sous la forme d'une liste
  de couples  \lstinline+(élément,nombre d'occurences)+.  On utilisera
  la   fonction   \lstinline+partition+   ainsi  que   les   fonctions
  \lstinline+fst+ et \lstinline+snd+.

\item Nous utiliserons  enfin une petite fonction qui  nous renvoie un
  élément aléatoirement  choisi dans un ensemble.  Nous en reparlerons
  dans le chapitre suivant.

\begin{lstlisting}
let rand_el = fun ens ->
  let t = Array.of_list (liste_el ens) in
  let n = Array.length t in
  let k = Random.int n in
  t.(k);;
\end{lstlisting}

Nopus  utilisons un  tableau  pour avoir  un accès  plus  rapide à  un
élément quelconque.
 
\end{enumerate}



\end{exercice}








%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=2.4cm]{sting}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.1cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


\begin{exercice}[Poker]
  
 Une main au poker est constituée de 5 cartes tirées d'un jeu de 52
 cartes. Deux lettres identiques (par exemple XX) correspondent à deux
 cartes de même hauteur (par exemple deux dames). 

\begin{enumerate}
\item 

\begin{enumerate}
\item Combien y a-t-il de mains contenant des carrés (XXXXY) ?  
\item des fulls (XXXYY) ?
\item des brelans (XXXYZ) ? 
\item des doubles paires (XXYYZ) ? 
\item des paires (XXYZA) ?
\item des quintes (cinq cartes dont les niveaux se suivent)?
\item des couleurs (5 cartes de la même couleurs quine soient pas des quintes)?
\item des quintes flush (des quintes d'une même couleur)?
\end{enumerate}

\item 

Nous pouvons calculer tout ça avec Caml.

Créons des  cartes: d'abord  des symboles, puis  des valeurs  puis des
cartes comme couples de valeurs. 


\begin{lstlisting}
type symbole = Trefle | Carreau | Coeur | Pique ;;

type valeur = Sept | Huit | Neuf | Dix | Valet | Dame | Roi | As ;;

type carte = C of valeur*symbole ;;
\end{lstlisting}

On crée deux ensembles de valeurs et de symboles:

\begin{lstlisting}
let vals =  ens_of_list [Sept;Huit;Neuf;Dix;Valet;Dame;Roi;As];;

let symbs = ens_of_list [Trefle;Carreau;Coeur;Pique];;
\end{lstlisting}

\begin{enumerate}
\item  Créez l'expression  \lstinline+cartes+  qui  est l'ensemble  de
  toutes les cartes du jeu et sera donc de type \lstinline+carte ens+.
La  définition  tient  en  une  ligne par  exemple  si  vous  utilisez
\lstinline+applatit+ et deux fois \lstinline+applique+... 

Vérifiez que:

\begin{lstlisting}
# cardinal cartes;;
- : int = 32
\end{lstlisting}
 
\item On appelle  ensuite \lstinline+mains+ l'ensemble des  mains de 5
  cartes qui est donc de type \lstinline+carte ens ens+.

Par exemple:

\begin{lstlisting}
# rand_el mains;;
- : carte ens =
Ens
 (C (As, Pique),
  Ens
   (C (As, Carreau),
    Ens
     (C (Valet, Carreau),
      Ens (C (Sept, Carreau), Ens (C (Sept, Trefle), Vide)))))
\end{lstlisting}

ou encore:

\begin{lstlisting}
# liste_el (rand_el mains);;
- : carte list =
[C (Huit, Trefle); C (Sept, Carreau); C (Dame, Coeur); C (As, Coeur); C (As, Pique)]
\end{lstlisting}

Expliquez le résultat suivant:

\begin{lstlisting}
# cardinal mains;;
- : int = 201376
\end{lstlisting}

\item Créez deux fonctions qui  renvoient respectivement la hauteur et
  la couleur d'une carte:

  \begin{lstlisting}
# hauteur;;
- : carte -> valeur = <fun>
# couleur;;
- : carte -> symbole = <fun>
  \end{lstlisting}

puis une fonction qui renvoie l'ensemble des valeurs d'une main:

\begin{lstlisting}
# hauteurs;;
- : carte ens -> valeur ens = <fun>
\end{lstlisting}

\item Il  ne reste plus  qu'à créer des  tests pour déterminer  si une
  main donnée correspond à une paire, deux paires, un brelan, etc.

Vous   pourrez    utiliser   par    exemple   \lstinline+List.exists+,
\lstinline+List.length+, \lstinline+List.filter+, \lstinline+List.sort compare+,
 \lstinline+List.split+,    et    nos   fonctions    \lstinline+plie+,
 \lstinline+applique+,     \lstinline+count+,     \lstinline+couleur+,
 \lstinline+hauteurs+,...

Par exemple:

\begin{lstlisting}
# count (applique est_brelan mains);;
- : (bool * int) list = [(true, 10752); (false, 190624)]

# count (applique est_quinte mains);;
- : (bool * int) list = [(true, 4080); (false, 197296)]
\end{lstlisting}


ou bien:

\begin{lstlisting}
# cardinal (filtre est_brelan mains);;
- : int = 10752

# cardinal (filtre est_quinte mains);;
- : int = 4080
\end{lstlisting}




\end{enumerate}


\end{enumerate}
\end{exercice}





























\begin{exercice}[Les boules]
  

\begin{enumerate}
\item Démontrez que  pour tous entiers naturels $n$ et $k$ tels que $2 \leqslant k <
n - 1$, on a :
\[C_{n-2}^{k-2} + 2 C_{n-2}^{k-1} + C_{n-2}^{k} = C_{n}^{k}.\]
\item On considère deux entiers naturels $n$ et $k$ tels que $2 \leqslant k <
n - 1$. On dispose d'une urne contenant $n$ boules indiscernables au toucher. Deux des boules sont rouges, les autres sont blanches.

On tire  au hasard et simultanément  $k$ boules de l'urne.  On appelle A
l'évènement « au moins une boule rouge a été tirée ».


Calculez de deux manières différentes le cardinal de A.


\end{enumerate}

\end{exercice}


\begin{exercice}[Pesées]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{roberval}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
  On dispose de 28 pièces de monnaie  dont une est fausse et a une masse
  légèrement supérieure aux autres.

Nous disposons uniquement d'une balance de Roberval et des 28 pièces.

En combien de pesées peut-on déterminer la fausse pièce?
\end{exercice}

\begin{exercice}[Sommes et cardinaux]
 Soit $E$ un ensemble fini de cardinal $n$.
Déterminer les sommes suivantes en fonction de $n$:
\begin{multicols}{3}
\begin{itemize}
\item[a)] $\underset{A\in\PR(E)}{\sum}\card A$.
\item[b)] $\underset{(A,B)\in\PR(E)^2}{\sum}\card\big(A\cap B\big)$.
\item[c)] $\underset{(A,B)\in\PR(E)^2}{\sum}\card\big(A\cup B\big)$.
\end{itemize}
\end{multicols}
\end{exercice}



\begin{exercice}[Permutations]
On   peut   être   amené   à  rechercher   les   \textit{cycles}   d'une
permutations.   Il  est   aisé  de   les  représenter   à   l'aide  de
\textit{graphes} orientés...cycliques.

Par exemple, si l'on considère la permutation:

$$
\begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
4&8&3&5&2&9&6&1&7
\end{pmatrix}
$$


alors on trouve trois cycles:


\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.2}
\Vertices{circle}{1,4,5,2,8}

\Edges[style={->}](1,4,5,2,8,1)
  \end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
    \SetGraphUnit{1.2}
\Vertices{circle}{6,7,9}
\Edges[style={->}](6,7,9,6)
  \end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}
    \SetGraphUnit{1.2}
\Vertex{3}
\Loop[dist=1cm,dir=NO,style={->}](3)
  \end{tikzpicture}
\end{center}


\begin{enumerate}

\item Décomposez $\pi=(2\ 1\ 3\ 5\ 4\ 7\ 9\ 6\ 8)$ en cycles.

\item La \textit{longueur} d'un cycle est le nombre de ses sommets.

Soit $p$  une permutation. On  note $p^k=p\circ p^{k-1}$  avec $p^0={\rm
id}$, la permutation identité.

 Soit  $p\in\mathfrak{S}_n$. On  définit  une  relation $\RR$  sur
      $E=\{1,2,...,n\}$  par:  $$i \RR  j  \Leftrightarrow  \exists k  \in
      \bbn^\star, \ p^k(i)=j$$

Est-ce que $\RR$ est une relation d'équivalence? Quels sont ses classes?



\item L'\textit{ordre}  d'une permutation  est  le plus  petit entier  naturel
strictement positif $k$ tel que $p^k={\rm id}$.

Déterminez l'ordre  de $\pi$.  Est-ce que toute  permutation a  un ordre
fini? Comment le calculer?
\end{enumerate}





\end{exercice}




\begin{exercice}[Permutations de bosses]
Voici une série de fonctions CAML: pourriez-vous dire ce qu'elles font?


\begin{lstlisting}
let f1  = fun p r -> 
  let rec aux = fun i acc ->
    let pi = List.nth p (i-1) in
    if pi = r then
      acc
    else
      aux pi (pi::acc)
  in aux r [r];;

let f2 = fun p ->
  List.fold_left (fun acc x -> if List.mem x (List.flatten acc) then acc else ((f1 p x)::acc)) [] p;;

let f3 = fun p ->
  List.map List.length (f2 p);;

let rec f4 = fun a b ->
  if a >= b then
    if b = 0 then
      a
    else
      f4 b (a mod b)
  else
    f4 b a;;

let f5 = fun a b ->
  (a*b)/(f4 a b);;

let f6 = fun liste ->
  List.fold_left f5 1 liste;;

let f7 p =
  f6 (f3 p);;
\end{lstlisting}




\end{exercice}




\begin{exercice}[Flavius Josèphe]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3.2cm]{quovadis}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.1cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
  

Flavius Josèphe (37  - 100) ou plutôt Yossef  ben Matityahou HaCohen est
un  historien romain  d'origine juive  et de  langue grecque  et  qui ne
devait pas être trop mauvais en  mathématiques si on en croit la sinistre
anecdote suivante. Lors de  la première guerre judéo-romaine, Yossef fut
piégé dans une grotte avec 39 autres de ses compagnons en juillet 67. Ne voulant pas
devenir esclaves, ils mirent  au point un algorithme d'auto-destruction:
il s'agissait de se mettre en cercle et de se
numéroter de  1 à 40. Chaque  septième devait être tué  jusqu'à ce qu'il
n'en  reste plus  qu'un qui  devait alors  se suicider.  Ce  dernier fut
Yossef lui-même...et il ne se suicida  pas! Après deux ans de prison, il
fut libéré, il  entra au service des romains  comme interprète et acquit
la citoyenneté romaine deux ans plus tard.
Quel numéro  portait Yossef? Créez  un programme CAML qui  donne l'ordre
des exécutions quelque soit le nombre de prisonniers et le nombre sinistre.



Dans une  autre situation (pour  ne pas  vous donner la  réponse quand
même...),  on  doit obtenir  avec  30  compagnons  et 6  comme  nombre
sinistre:


\begin{lstlisting}
# flavius 30 6;;
- : int list * string =
([6; 12; 18; 24; 30; 7; 14; 21; 28; 5; 15; 23; 2; 11; 22; 3; 16; 27; 10; 26;
  13; 1; 20; 17; 9; 19; 29; 25; 8],
 "survivant : no 4")
\end{lstlisting}




\end{exercice}



\begin{exercice}[Nombre de \textsc{Catalan}]
  De combien de  manières peut-on parenthéser le produit  de 4 nombres
  (par  exemple  $(a((bc)d))$:  on  calcule  $bc$  puis  $(bc)d$  puis
  $a((bc)d)$...)?

On  peut utiliser  une  pile pour  effectuer ce  calcul,  ou un  arbre
binaire  syntaxique,  ou  des  diagonales  dans  un  polygone  qui  le
découpent en triangles, ou un
cheminement dans un réseau...Toutes ces représentations sont liées par
des bijections.

Représentez toutes les situations pour 4 nombres.


Pour $n$ nombres, on peut montrer  qu'il y a $ \frac{1}{n+1} C_{2n}^n$
possibilités:  c'est   le  nombre  de  \textsc{Catalan},   du  nom  du
mathématicien franco-belge Eugène Charles \textsc{Catalan} (1814-1894) expulsé de
l'école  Polytechnique  en  1834  pour ses  idées  politiques  trop  à
gauche...


%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{Catalan_bijections}
\end{center}
%\end{figure}


Que pensez-vous  du calcul  suivant? En quoi  peut-il nous  être utile
pour le problème précédent?

Soit $(c_n)$ la suite définie par $c_0=1$ et pour tout $n\geqslant 1$:
$c_{n}=\frac{4n-2}{n+1}c_{n-1}$.  

Soit $P_n(X)=\sum_{k=0}^n c_kc_{n-k}X^{k+1}$.

Montrons que $P_n(1)=c_{n+1}$.

On le vérifie au rang $n=0$.

On peut  donc faire l'hypothèse  qu'il existe  au moins un  entier $n$
pour lequel la propriété est vraie. 

On vérifie 
que $X^{n+2}P_n(\frac 1X)=P_n(X)$.

 En dérivant on obtient:
$$(n+2)X^{n+1}P_n(\frac 1X)-X^nP_n'(\frac 1X)=P_n'(X)$$
on      en       déduit      alors       que      $P_n'(1)=\frac{n+2}2
P_n(1)=\frac{n+2}2c_{n+1}$. D'autre part:
\begin{align*}  P_{n+1}'(X) &=  \sum_{k=0}^{n+1}(k+1)c_kc_{n+1-k}X^k\\
&=        c_{n+1}+\sum_{k=1}^{n+1}(4k-2)c_{k-1}c_{n+1-k}X^k\\       &=
c_{n+1}+\sum_{p=0}^{n}(4p+2)c_pc_{n-p}X^{p+1}\\                     &=
c_{n+1}+4\sum_{p=0}^{n}(p+1)c_pc_{n-p}X^{p+1}-2\sum_{p=0}^{n}c_pc_{n-p}X^{p+1}\\
&=c_{n+1}+4XP_n'(X)-2P_n(X)
\end{align*} D'où:
$$P_{n+1}'(1)=\frac{n+3}2P_{n+1}(1)=c_{n+1}+4P_n'(1)-2P_n(1)=c_{n+1}+2(n+2)P_n(1)-2P_n(1)=(2n+3)c_{n+1}$$
et par  conséquent $P_{n+1}(1)=\frac{4n+6}{n+3}c_{n+1}=c_{n+2}$. C'est
la relation au rang $n+1$...

\end{exercice}

\vfill

\eject




\begin{exercice}[Tests naïfs sur le générateurs aléatoires]
  
  \begin{enumerate}
  \item  La fonction  \lstinline+lsr+ décale  l'écriture binaire  d'un
    entier vers la droite. Par exemple:

    \begin{lstlisting}
# 16 lsr 2;;
- : int = 4
    \end{lstlisting}

Expliquez:

\begin{lstlisting}
# 16 lsl 2;;
- : int = 64
\end{lstlisting}

Quant à \lstinline+lxor+, elle effectue xor bit à bit de deux chaînes.

Expliquez:


\begin{lstlisting}
# 15 lxor 8;;
- : int = 7
# 15 lxor 16;;
- : int = 31
\end{lstlisting}

Créez une fonction  \lstinline+explose+ qui renvoie la  chaîne de bits
de l'écriture en  base 2 d'un entier en n'utilisant  que les fonctions
précédentes (sans opérateur arithmétique \lstinline|+, mod, /,|... 
).

\begin{lstlisting}
# explose 13;;
- : int list = [1; 1; 0; 1]
\end{lstlisting}

\item Créez une fonction \lstinline+n_prems = fun n liste+ qui renvoie
  le  couple  formé   de  la  liste  des  $n$   premiers  éléments  de
  \lstinline+liste+ et de la liste des éléments restants.

  \begin{lstlisting}
# n_prems 2 [1;2;3;4;5;6];;
- : int list * int list = ([1; 2], [3; 4; 5; 6])
# n_prems 6 [1;2;3;4;5;6];;
- : int list * int list = ([1; 2; 3; 4; 5; 6], [])
# n_prems 7 [1;2;3;4;5;6];;
- : int list * int list = ([], [])
  \end{lstlisting}


\item Créez ensuite une fonction \lstinline+par_paquets = fun long liste+
 qui découpe une liste en paquets de longueur constante:

  \begin{lstlisting}
# par_paquets 2 [1;2;3;4;5;6];;
- : int list list = [[1; 2]; [3; 4]; [5; 6]]
# par_paquets 4 [1;2;3;4;5;6];;
- : int list list = [[1; 2; 3; 4]]
# par_paquets 7 [1;2;3;4;5;6];;
- : int list list = []
  \end{lstlisting}


\item Créez  une fonction \lstinline+  count = fun liste+  qui renvoie
  la listes des couples (éléments,effectif).

Par exemple:
  \begin{lstlisting}
# count ['a';'a';'b';'a';'c';'b';'d';'d';'a';'d'];;
- : (char * int) list = [('d', 3); ('c', 1); ('b', 2); ('a', 4)]
  \end{lstlisting}


On pourra  utiliser la fonction \lstinline+List.partition+  dont voici
la description:

\begin{lstlisting}
val partition : ('a -> bool) -> 'a list -> 'a list * 'a list

partition p l returns a pair of lists (l1, l2), where l1 is the list of all the elements of l that satisfy the predicate p, and l2 is the list of all the elements of l that do not satisfy p. The order of the elements in the input list is preserved.
\end{lstlisting}


\item On utilisera  très souvent dans ce chapitre  la fonction décrite
  ci-dessous:


\begin{lstlisting}[caption={}]
val int : int -> int

Random.int bound returns a random integer between 0 (inclusive) and bound (exclusive). bound must be greater than 0 and less than 2^30.
\end{lstlisting}

Comment est généré \lstinline+Random.int+?  Tous les langages ont leur
fonction  random.  Comment  sont-elles crées?  Beaucoup  utilisent  un
\textit{générateur  congruentiel  linéaire},  c'est-à-dire  quelque  chose  qui
fabrique une suite du type:

$$x_{n+1} = ( a \cdot x_n + c ) \mod m$$

avec $a$, $c$ et $m$ des entiers judicieusement choisis.

Le premier  terme $x_0$  est appelé la  \textit{graine} (\textit{seed}
en anglais de spécialité...)

Il existe quelques générateurs célèbres:

\begin{itemize}
\item  $X_{n+1} =(129  X_n +  907633385) \mod  2^{32}$ utilisé  par le
  Turbo-Pascal mais qui a de gros défauts;
\item $X_{n+1} = (1103515245 X_n + 12345) \mod 2^{31}$ utilisé par les
  systèmes UNIX  mais dont il  ne faut retenir  que les bits  de poids
  fort.
\item $X_{n+1} = (22 695 477 X_n+1 ) \mod 2^{32} $ en C++.
\item  $X_{n+1}  =  (  1664525  X_n +  1013904223  )  \mod  2^{32}  $:
  générateur de \textsc{Knuth-Lewis}.
\end{itemize}

Il faut absolument lire le volume 2 de \og \textit{The Art of Computer
  Programming}\fg{} de Don \textsc{Knuth} pour étudier correctement le
problème.

Nous nous contenterons d'une approche expérimentale.

\item Expliquez le code suivant:


  \begin{lstlisting}[caption={}]
let suite1 = fun nb graine ->
  let rec aux = fun k kn acc ->
    if k = nb then
      List.flatten acc
    else
      aux (k + 1) ((1664525 * kn + 1013904223) mod (1 lsl 32)) ((explose kn)::acc)
  in aux 0 graine [];;
  \end{lstlisting}

Comment tester la nature aléatoire  d'un générateur avec les fonctions
mises au point précédemment?

Testez plusieurs générateurs et en particulier celui de OCaml!

On utilise aussi très souvent le \textit{Poker test}: demandez à votre
professeur adoré de quoi il retourne...

  \end{enumerate}


\end{exercice}


%%% Local Variables: 
%%% TeX-master: "Poly_Probas_Stats_13"
%%% End: 
