% xmeuris.tex (gH) :
\documentclass[a4paper,12pt]{article}
\parindent 0cm
\parskip   0.2cm
%
\begin{document}
\thispagestyle{empty}
%
{\Large \begin{center}\textsc{Partie Informatique}\end{center}}

\vspace{1cm}
Soit $E$ l'ensemble des entiers de 1 \`{a} $n$.
On appelle partie dissoci\'{e}e de $E$ tout sous-ensemble
de $E$ qui ne contient pas deux entiers cons\'{e}cutifs. On
note $w_n$ le nombre de tels sous-ensembles en g\'{e}n\'{e}ral
et $w_{n,k}$ le nombre de tels sous-ensembles de $E$ qui
ont exactement $k$ \'{e}l\'{e}ments.

On d\'{e}signe par $F$ l'ensemble des nombres binaires \`{a}
$n$ chiffres. Soit $h$ l'application de ${\mathcal{P}}(E)$ dans F qui \`{a} un
sous-ensemble $A$ de $E$ associe le nombre $N$
tel que le $j$-i\`{e}me chiffre (\`{a} partir de la droite) de $N$ est $1$ si $j\in A$.
Ainsi pour $E=\{1,2,3,4\}$, $A=\{1,3,4\}$, $h(A)=1101$ en base 2.

\begin{enumerate}
\item
Donner explicitement $w_1$, $w_2$ et $w_3$ (on fournira
aussi les parties dissoci\'{e}es correspondantes).

\item
Montrer que $h$ est une bijection.

\item
Donner un algorithme qui \'{e}tant donn\'{e} un tableau $A$ dont les $nb(A)$ \'{e}l\'{e}ments not\'{e}s $A[i]$ sont
ordonn\'{e}s, renvoie le nombre $h(A)$. On optimisera le nombre d'op\'{e}rations.

\item
Montrer que $w_{n,k}=C_a^b$ pour $a$ et $b$ bien choisis
en remarquant que dans un mot d'une partie dissoci\'{e}e de $E$ \`{a} $k$ \'{e}l\'{e}ments
le chiffre 1 est enti\`{e}rement d\'{e}termin\'{e} par la place du z\'{e}ro qui le
pr\'{e}c\'{e}de (s'il existe).

\item
En d\'{e}duire la valeur de $w_n$, $w_n+w_{n+1}$ et fournir la forme compacte
de $w_n$.

\item
Donner un algorithme de calcul de $u_n$ en temps constant bas\'{e} sur cette forme compacte ;
on supposera
$u_0$ et $u_1$ donn\'{e}s, par deux variables $a$ et $b$.
\end{enumerate}

On rappelle que pour une suite lin\'{e}airement r\'{e}curente
$u_n=\displaystyle \sum_{i=1}^k a_i.u_{n-i}$
la forme compacte est donn\'{e}e par l'expression
$u_n = \displaystyle \sum_{i=1}^r\ \rho_i^n.P_i(n)$ o\`{u} $\rho_i$
est une racine de l'\'{e}quation caract\'{e}ristique associ\'{e}e \`{a} $(u_n)_{n\in N}$ :
$$(E)\ :\ x^n= \displaystyle \sum_{i=1}^k a_i.x^{n-i}$$
et o\`{u} $P_i$ est un polynome de degr\'{e} strictement inf\'{e}rieur \`{a} la multiplicit\'{e}
de $\rho_i$, $r$ d\'{e}signant le nombre de racines distinctes de $(E)$.
\end{document}
