% 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{2cm}
Soit $E$ l'ensemble des entiers de 1 à $n$.
On appelle partie dissociée de $E$ tout sous-ensembles $T$
de $E$ qui ne contient pas deux entiers consécutifs. On
note $w_n$ le nombre de tels sous-ensembles en général
et $w_{n,k}$ le nombre de tels sous-ensembles de $E$ qui
ont exactement $k$ éléments.

Donner explicitement $w_1$, $w_2$ et $w_3$ (on fournira
aussi les sous-ensembles correspondants).

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

Montrer que $h$ est une bijection.

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 de $E$ à $k$ éléments
le chiffre 1 est entièrement déterminé par la place du zéro qui le
précéde (s'il existe).

En déduire la valeur de $w_n$, $w_n+w_{n+1}$ et fournir la forme compacte
de $w_n$. On rappelle que pour une suite linéairement récurente
$u_n=\displaystyle \sum_{i=1}^k a_i.u_{n_i}$
la forme compacte est donnée par l'expression
$u_n displaystyle \sum{i=1}^r\ \rho^n.P_i(n)$ où $\rho_i$
est une racine de l'équation caractéristique associée à $(u_n)_{n\in N$ :
$x^n= \displaystyle \sum_{i=1}^k a_i.x^{n-i}$
et où $P_i$ est un polynome de degré strictement inférieur à la multiplicité
de $\rho_i$.
\end{document}