\documentstyle[11pt,fullpage]{article}
\parskip=2.5pt plus 0.5 pt minus 0.5pt
\parindent=0pt
\def\ds{\displaystyle}
\newcommand{\Frac}[2]{\frac{\ds{#1}}{\ds{#2}}}
\def\deg{\hbox{deg}}
\def\hat {\widehat}
\def \pn {\par \noindent}
\def\bar{overline}


\newcounter{quesno}

\newcommand{\Q}{\addtocounter{quesno}{1}\goodbreak\goodbreak{\bf Q\thequesno.}}
\newcommand{\R}[2]{\begin{itemize}\item[$\Box$] #1 \par \item[$\Box$]
        #2 \end{itemize} \par.\dotfill.\par.\dotfill.}



\begin{document}

\begin{center}
{\Large \bf\sf DEA d'ALGORITHMIQUE 1998-1999} \\
{\large\bf\sf Analyse d'algorithmes: Mod\`eles combinatoires}\\
{\tt Philippe.Flajolet@inria.fr}\\
{\tt http://algo.inria.fr/flajolet/Teach/}
\end{center}

{\sc R\`egle du jeu.}
R\'ediger votre copie en au plus deux heures et trente minutes
au total pour
les exercices~I et II, et en au plus 30 minutes pour le QCM.
Ceux qui le souhaitent pourront ensuite compl\'eter
leurs r\'eponses aux exercices sur feuillets s\'epar\'es 
clairement marqu\'es comme tels.
\begin{quote}
Postez vos copie le {\bf jeudi 11 mars 1999} au plus tard \`a:
\\
Philippe Flajolet,\\
(DEA ALGO) \\
INRIA Rocquencourt\\
F-78153 Le Chesnay 
\end{quote}
{\bf Pensez a garder une copie pour vous au cas o\`u $\cdots$}

\bigskip

\begin{center}
\sc Partie I. Pr\'edictions et scrutins
\end{center}

{\em 
Le probl\`eme des pr\'edictions de 
r\'esultats de scrutin consiste \`a observer de
mani\`ere partielle un d\'epouillement de sorte \`a tenter de
pr\'edire avec bonne probabilit\'e ce qui va en \^etre le r\'esultat
final. Ce probl\`eme statistique
est le ``probl\`eme inverse'' du probl\`eme de probabilit\'es
discr\`etes suivant:
``On consid\`ere 2 candidates en lice appell\'es
Arlette et Bernadette.
Qu'observe-t-on au cours du d\'epouillement?''
}

Soit ${\cal A}=\{a,b\}$ un alphabet \`a deux lettres. 
la taille d'un mot est sa longueur.
On utilise les m\^emes lettres pour un langage, sa s\'erie
g\'en\'eratrice, et la suite des coefficients correspondants.
On consid\`ere les langages suivants:
\begin{itemize}
\item[---] ${\cal W}=\{a,b\}^\star$ est le langage de tous les mots;
\item[---] $\cal E$ est le langage des mots contenant autant de $a$ que 
de $b$: ${\cal E}=\{\epsilon, ab, ba, aabb, bbaa, abab,\ldots\}$; 
\item[---] $\cal P$ est le sous ensemble des mots $w$ de $E$ tels que, de plus,
dans tout prefixe de $w$ le nombre de $a$ soit toujours sup\'erieur ou
 \'egal au au nombre de $b$:
${\cal P}=\{\epsilon,ab,aabb,abab,\ldots\}$;
\item[---] $\cal Q$ est le langage obtenu \`a partir de $\cal P$ en
echangeant le r\^ole des lettres $a$ et $b$.
\end{itemize}
On pourra s'aider d'un dessin ou un mot est repr\'esent\'e par une
ligne polygonale partant de $(0,0)$, la lettre $a$ \'etant cod\'ee par
l'ajout du vecteur $(1,1)$ et la lettre $b$ par l'ajout de $(1,-1)$.
Il n'est pas n\'ecessaire de d\'etailler les calculs interm\'ediaires
et on peut s'appuyer sur un syst\`eme de calcul formel
pour l'obtention des r\'esulats.

{\bf Q1.} Donner la s\'erie g\'en\'eratrice 
$W(z)$. Observer que ${\cal P}$ v\'erifie l'equation
\[
{\cal P}={\tt Seq}(a\cdot {\cal P} \cdot b),
\]
et en d\'eduire $P(z)$.
Montrer une fois pour toutes que pour toute s\'erie $f(z)$, on a:
$[z^{2n}]f(z^2)=[z^n]f(z)$.
Expliciter le coefficient $P_{2n}=[z^{2n}]P(z)$.

{\bf Q2.} Montrer que
\[
{\cal E} = {\tt Seq}\left( (a\cdot{\cal P}\cdot b)
\cup (b \cdot {\cal Q}\cdot a )\right).
\]
En d\'eduire la s\'erie g\'en\'eratrice $E(z)$ ainsi que  $E_{2n}$.

\'Evaluer exactement et estimer asymptotiquement le quotient
\[
\frac{P_{2n}}{E_{2n}},
\]
lequel donne la probabilit\'e qu'Arlette ne soit jamais domin\'ee par
Bernadette au cours du d\'epouillement, sachant qu'Arlette et Bernadette
sont \`a \'egalit\'e de votes.

{\bf Q3.} Soit $E_{n,k}$ le nombre de mots de ${\cal E}_n$ ayant
exactement $k$
pr\'efixes (de longueur entre 1 et $n$)
qui sont dans $\cal E$, et $E(z,u)=\sum_{n,k} E_{n,k}z^n u^k$.
Graphiquement, il s'agit des lignes polygonales touchant $k$ fois l'axe
horizontal. Montrer que 
\[
E(z,u)=\frac{1}{1-uz^2(P(z)+Q(z))}.
\]
On pose 
\[
\mu_{2n} := 
\frac{1}{E_{2n}} [z^{2n}] \left(\frac{\partial}{\partial u}
E(z,u)\right)_{u=1}.
\]
Justifier d'abord que $\mu_{2n}$ est l'esp\'erance du nombre
de fois o\`u Arlette et Bernadette sont \`a \'egalit\'e au cours du
d\'epouillement, sachant qu'elles ont recueilli un
nombre \'egal de voix.

Utiliser les expressions exactes ou l'analyse de
singularit\'e pour obtenir un equivalent asymptotique de 
$\mu_{2n}$.

{\bf Q4.} Pour un scrutin particulier $w=w_1\cdots w_{2n}\in\cal E$,
soit $\chi[w]$ la valeur du premier indice $j$ avec $0\le j<n$
tel que 
$w_1\cdots w_{j+1}$ comporte plus de $b$ que de $a$;
on pose $\chi[w]=n$ si un tel indice n'existe pas. (On mesure donc
la dur\'ee  de la p\'eriode initiale o\`u Arlette domine 
Bernadette.)
 Par exemple, $\chi[baab]=0$,
$\chi[aabbbba]=4$, $\chi[aaababbb]=8$. 
Soit 
\[
F(z,v):=\sum_{w\in\cal E} z^{|w|}v^{\chi(|w|)}.
\]
Montrer que
\[
F(z,v)=1/(1-(z^2v^2P(zv)+z^2Q(z)))
\]
En d\'eduire la valeur exacte et asymptotique de l'esp\'erance
\[
\nu_{2n}= \frac{1}{E_{2n}}[z^{2n}]
\left(\frac{\partial}{\partial v}F(z,v)\right)_{v=1}.
\]

\clearpage


\begin{center}
\sc Partie II. Mod\`eles d'urnes
\end{center}

{\em On donne ici une approche combinatoire \`a un
mod\`ele de transfert de particules et de chaleur \'etudi\'e par
P\'olya et Ehrenfest.}


{\bf Q1.} Le nombre de mani\`eres de placer les $n$ \'el\'ements
$\{1,2,\ldots,n\}$ dans  $k$ urnes distingu\'ees, avec chaque urne
contenant un nombre pair de boules (possiblement \'egal \`a~0), vaut
\[G_{n,k}={n!}
\, [z^n](\cosh z)^k,\]
o\`u $\cosh(z)=(e^z+e^{-z})/2$. 

Montrer que
$(\cosh z)^k$ se d\'eveloppe en une combinaison lin\'eaire
finie d'exponentielles de la forme $e^{\alpha z}$.
Exprimer $G_{n,k}$.

{\bf Q2.} Soit $f(z)=\sum_n f_n z^n/n!$ une s\'erie g\'en\'eratrice
exponentielle, $\widetilde f(z)=\sum_n f_n z^n$ la s\'erie ordinaire
correspondante. D\'eterminer $\widetilde f(z)$ lorsque
\[f(z)=e^{\alpha z},\quad f(z)=\cosh(z),\quad f(z)=ze^z.\]
Montrer que la transformation $f\mapsto \widetilde f$ est lin\'eaire.

D\'eterminer la s\'erie g\'en\'eratrice
ordinaire $\widetilde f(z)$ correspondant \`a $f(z)=(\cosh(z))^k$
sous forme de d\'ecomposition en \'el\'ements simples.

Obtenir un \'equivalent asymptotique de $G_{2n,k}$ lorsque
$k$ est fix\'e et $n$ tend vers l'infini.

{\bf Q3.} Deux cavit\'es appel\'ees $A$ et $B$
contenant au total $k$ particules (distinctes) sont en 
communication par un trou tr\`es fin. A chaque seconde, une particule passe
de $A$ \`a $B$ ou inversement.
 Au temps $0$, la cavit\'e $A$ est vide et la cavit\'e $B$
est pleine.

Donner la s\'erie g\'en\'eratrice des fonctions de $\{1,\ldots,n\}$
dans
$\{1,\ldots,k\}$ telles que l'image inverse de tout $j\in[1,k]$ soit
de taille paire.

On postule que toutes 
les \'evolutions possibles en $n$ \'etapes sont \'equiprobables.
Relier le probl\`eme aux questions pr\'ec\'edentes.

Justifier par la m\'ethode de votre choix
que la s\'erie g\'en\'eratrice exponentielle de toutes ces
\'evolutions vaut $e^{kz}$.


D\'eterminer un \'equivalent asymptotique en grand temps de la
probabilit\'e que la cavit\'e $A$ soit vide au bout de $n$ \'etapes.

{\bf Q4.} La s\'erie g\'n\'eratrice exponentielle des \'evolutions qui
aboutissent \`a avoir $r$ particules dans la cavit\'e~$A$ vaut
\[
{k \choose r} (\cosh z)^{k-r} (\sinh z)^r.
\]
Justifier ce r\'esultat.

\medskip


D\'eterminer les deux premiers termes du
d\'eveloppement 
asymptotique $(n\to+\infty)$ de l'esp\'erance $E_n$ de la variable
al\'eatoire  
repr\'esentant le nombre d'atomes contenus dans l'urne~$A$ au
temps $n$; d\'eterminer ainsi a quelle vitesse on se ``rapproche 
de l'\'equilibre''.
(Suggestion: former une s\'erie bivari\'ee o\`u $u$ marque les
diff\'erentes valeurs possible de $r$.)

\clearpage

\begin{center}
\bf III. QUESTIONNAIRE
\end{center}

{\em Cochez une case et justifiez en au plus deux lignes votre choix.}

{\Q} Soit $A(z)$ la s\'erie g\'en\'eratrice ordinaire
d'une classe $\cal A$. Soit $\cal C$ la classe des paires
ordonn\'ees $(\alpha,\beta)$ d'\'el\'ements de
$\cal A$ telles que $|\alpha|=|\beta|$. Alors
la s\'erie g\'en\'eratrice ordinaire de $\cal C$ v\'erifie:
\R{$\ds C(z)=\sum_n (A_nz^n)^2 $}
{$\ds C(z)=\left(\sum_n A_n z^n\right)^2$}

{\Q} Le nombre $X_n$ d'arbres unaires-binaires (dont les sommets ot
degr\'e 0, 1, ou 2)
comportant deux fois plus de
sommets binaires que de feuilles (sommets de degr\'e 0) v\'erifie
\R{$\ds{\frac{X_n}{2^n}\to+\infty}$}
{$\ds{\frac{X_n}{2^n}\to+0}$}


{\Q} Le nombre de partitions de $n$ en sommants premiers,
c-\`a-d le nombre des $(\nu_1,\nu_2,\ldots,\nu_k)$ avec
$\nu_1\le\nu_2\le\cdots\le\nu_k$, $\nu_1+\cdots+\nu_k=n$,
chaque $\nu_j\in\{2,3,5,\ldots\}$,
a pour s\'erie g\'en\'eratrice ordinaire (OGF)
\R{$\ds{\prod_{p~\hbox{premier}}\frac{1}{1-z^p}}$}
{$\ds{\frac{1}{1-\sum_{p~\hbox{premier}}z^p}}$}

{\Q} Le nombre de compositions de l'entier
$n$ en sommants qui sont des puissances de
2, c-\`a-d le nombre des $(\nu_1,\nu_2,\ldots,\nu_k)$ avec
$\nu_1+\cdots+\nu_k=n$,
chaque $\nu_j\in\{1,2,4,8,\ldots\}$
a pour s\'erie g\'en\'eratrice ordinaire (OGF)
\R{$\ds{\sum_{n=0}^\infty {z^{2^n}\over 1-z^{2^n}}}$}
{$\ds{\frac{1}{1-\sum_{n=0}^\infty z^{2^n}}}$}

{\Q} Une ``quasi-permutation'' est un objet \'etiquet\'e (EGF)
defini comme un ensemble de cycles
non-orient\'es (de taille $\ge1$).
La s\'erie g\'en\'eratrice exponentielle des quasipermutations est:
\R{$\ds{\frac{e^{z/2}}{\sqrt{1-z}}}$}
{$\ds{\frac{e^{-z/2}}{1-z}}$}

{\Q} On consid\`ere
$\ds{f_n=[z^n]e^{-1+e^{-1+e^z}}}=[z^n]\exp(-1+\exp(-1+e^z))$. Alors: 
\R{$f_n\to 0$}{$f_n\to\infty$}

{\Q} Soit $\ds{ h_n=[z^n]\log\frac{1}{1-z/2}e^{z^2+z^3}}$. Alors:
\R{$h_n\sim e^{12} 2^{-n}/n$}{$h_n\sim e^{-12} 2^{n}/n$}
{\Q} On rappelle que $\ds [z^n]\frac{1}{\sqrt{1-z}}\sim
\frac{1}{\sqrt{\pi n}}$ et $\ds {[z^n]\log \frac{1}{1-z}=
\frac{1}{n}}$. Soit $\ds{k_n=[z^n]\frac{1}{\sqrt{1-3z}}
\log\frac{1}{1-2z}}$. Alors:
\R{$\ds{k_n\sim \log 3 \frac{3^n}{\sqrt{\pi n}}}$}
{$\ds{k_n\sim \sqrt{2} \frac{2^n}{n}}$}

{\Q} La probabilit\'e $p_n$ q'un mot binaire de longueur $n$
contienne au moins une fois le motif $abb$ v\'erifie:
\R{$p_n\to 1$}{$\ds p_n\to\frac{1}{8}$}

{\Q} \'Etant donn\'e un graphe connexe dont un sommet source $a$ et un
sommet destination $b$ ont \'et\'e distingu\'es. Soit $L_n$ le nombre
de chemins de $a$ \`a $b$ dans le graphe ayant
longueur $n$. Alors:
\R{$\ds \sum_n L_n z^n$ est une fraction rationnelle}
{$\ds \sum_n L_n \frac{z^n}{n!}$ est une fraction rationnelle}



\end{document}