% 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$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Attention : 0 n'est pas dans E
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
On appelle partie dissoci\'{e}e de $E$ tout sous-ensemble
de $E$ qui ne contient pas deux entiers cons\'{e}cutifs.
Ainsi \O, $\{i\}$ et $\{i,i+2\}$ sont des
parties dissoci\'{e}es de $E$ (si $n\geq 3)$.
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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Attention : on omet le mot "pairs" et les élèves démontrent un th. faux !
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\`{a} $n$ chiffres, y compris les blancs de t\^{e}te comme
pour $1=001$ si $n=3$. 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,0}$, $w_{2,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 par ordre
croissant, renvoie le nombre $h(A)$. On optimisera le nombre d'op\'{e}rations.
Ainsi pour $nb(A)=2$ avec $A[1]=3$  et $A[2]=5$, on trouvera $h(A)=2^3+2^5$
en 5 multiplications.

\item
On admettra que $w_{n,k}=C_{n+1-k}^k$ et donc que la forme compacte de
$w_n$ est~: $w_n=w_{n-1}+w_{n-2}$
(car $w_n$ correspond aux chiffres dont l'\'{e}criture binaire ne contient pas
deux chiffres 1 cons\'{e}cutifs).
Donner un algorithme de calcul de $w_n$ en temps constant bas\'{e}
sur cette forme compacte~; on supposera
$w_0$ et $w_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_{j=1}^r\ \rho_j^n.P_j(n)$ o\`{u} $\rho_j$
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_j$ est un polynome de degr\'{e} strictement inf\'{e}rieur \`{a} la multiplicit\'{e}
de $\rho_j$, $r$ d\'{e}signant le nombre de racines distinctes de $(E)$.
\end{document}
