Pour $n\in\mathbb N$, on note $\llbracket1,n\rrbracket$ l'ensemble des entiers de $1$ à $n$ (vide si $n=0$). Une partie de $\llbracket1,n\rrbracket$ est dite creuse si elle ne contient pas deux entiers consécutifs. On note $u_n$ le nombre de parties creuses de $\llbracket1,n\rrbracket$ et, pour $k\in\mathbb N$, $c_{n,k}$ le nombre de parties creuses à $k$ éléments. La suite de Fibonacci est définie par $F_0=0$, $F_1=1$ et $F_{m+2}=F_{m+1}+F_m$.
- Calculer $u_0$, $u_1$, $u_2$, $u_3$.
- Montrer que $u_{n+2}=u_{n+1}+u_n$ pour tout $n\in\mathbb N$.
- En déduire que $u_n=F_{n+2}$, puis calculer $u_{10}$.
- Soit $n\ge1$ et $k\in\llbracket1,n\rrbracket$. À une partie creuse $A=\{a_1<\dots<a_k\}$ de $\llbracket1,n\rrbracket$, on associe $\psi(A)=\{a_i-(i-1)\mid i\in\llbracket1,k\rrbracket\}$. Montrer que $\psi$ est une bijection de l'ensemble des parties creuses à $k$ éléments sur $\mathcal P_k(\llbracket1,n-k+1\rrbracket)$. En déduire $c_{n,k}$.
- En déduire que, pour $n\ge1$, $F_{n+2}=\sum_{k=0}^n\binom{n-k+1}{k}$, et contrôler pour $n=4$.
- De combien de façons peut-on choisir $3$ jours de garde parmi $10$ jours consécutifs, sans jamais deux jours de garde consécutifs ?
Pour la question 2, découper selon que la partie contient $n+2$ ou non.
Si une partie creuse contient $n+2$, elle ne contient pas $n+1$.
Une partie $\{a_1<\dots<a_k\}$ est creuse si et seulement si $a_{i+1}-a_i\ge2$ pour tout $i$ ; que devient cette condition pour $b_i=a_i-(i-1)$ ?
-
$\llbracket1,0\rrbracket=\varnothing$ n'a que la partie $\varnothing$, qui est creuse : $u_0=1$. Pour $n=1$ : $\varnothing$ et $\{1\}$, donc $u_1=2$. Pour $n=2$ : $\varnothing$, $\{1\}$, $\{2\}$ (la partie $\{1,2\}$ est exclue), donc $u_2=3$. Pour $n=3$ : $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,3\}$, donc $u_3=5$.
-
Soit $n\in\mathbb N$ et $\mathcal C_m$ l'ensemble des parties creuses de $\llbracket1,m\rrbracket$. On partage $\mathcal C_{n+2}$ en deux parties disjointes.
- Les parties creuses ne contenant pas $n+2$ sont exactement les parties creuses de $\llbracket1,n+1\rrbracket$ : il y en a $u_{n+1}$.
- Si $A\in\mathcal C_{n+2}$ contient $n+2$, elle ne contient pas $n+1$, donc $A\setminus\{n+2\}$ est une partie creuse de $\llbracket1,n\rrbracket$. Réciproquement, si $B\in\mathcal C_n$, alors $B\cup\{n+2\}$ est creuse, car les éléments de $B$ sont au plus égaux à $n$, donc aucun ne vaut $n+1$. Les applications $A\mapsto A\setminus\{n+2\}$ et $B\mapsto B\cup\{n+2\}$ sont réciproques l'une de l'autre : il y a $u_n$ telles parties.
Le principe additif donne $u_{n+2}=u_{n+1}+u_n$.
- On montre par récurrence double que $u_n=F_{n+2}$. Initialisation : $F_2=1=u_0$ et $F_3=2=u_1$. Hérédité : si $u_n=F_{n+2}$ et $u_{n+1}=F_{n+3}$, alors $u_{n+2}=F_{n+3}+F_{n+2}=F_{n+4}$.
Les termes $F_0,\dots,F_{12}$ sont $0,1,1,2,3,5,8,13,21,34,55,89,144$, d'où $u_{10}=F_{12}=144$.
- Une partie $A=\{a_1<\dots<a_k\}$ de $\llbracket1,n\rrbracket$ est creuse si et seulement si $a_{i+1}-a_i\ge2$ pour $1\le i<k$. Posons $b_i=a_i-(i-1)$.
- On a $b_{i+1}-b_i=a_{i+1}-a_i-1\ge1$, donc $b_1<\dots<b_k$ et $\psi(A)$ a $k$ éléments. De plus $b_1=a_1\ge1$ et $b_k=a_k-k+1\le n-k+1$. Ainsi $\psi(A)\in\mathcal P_k(\llbracket1,n-k+1\rrbracket)$.
- Réciproquement, si $B=\{b_1<\dots<b_k\}\subset\llbracket1,n-k+1\rrbracket$, on pose $a_i=b_i+i-1$. Alors $a_{i+1}-a_i=b_{i+1}-b_i+1\ge2$, $a_1=b_1\ge1$ et $a_k=b_k+k-1\le n$ : $\{a_1<\dots<a_k\}$ est une partie creuse à $k$ éléments de $\llbracket1,n\rrbracket$, et son image par $\psi$ est $B$.
Les deux constructions sont réciproques l'une de l'autre : $\psi$ est une bijection et $c_{n,k}=\binom{n-k+1}{k}$ (ce nombre est nul si $k>n-k+1$). Pour $k=0$, seule $\varnothing$ convient : $c_{n,0}=1=\binom{n+1}{0}$.
-
Les parties creuses de $\llbracket1,n\rrbracket$ se répartissent selon leur cardinal $k\in\llbracket0,n\rrbracket$ (cas disjoints et exhaustifs), d'où $$F_{n+2}=u_n=\sum_{k=0}^nc_{n,k}=\sum_{k=0}^n\binom{n-k+1}{k}.$$ Contrôle pour $n=4$ : $\binom50+\binom41+\binom32+\binom23+\binom14=1+4+3+0+0=8=F_6$.
-
En numérotant les jours de $1$ à $10$, un choix convenable est une partie creuse à $3$ éléments de $\llbracket1,10\rrbracket$ : il y en a $c_{10,3}=\binom{8}{3}=56$.
$u_0=1$, $u_1=2$, $u_2=3$, $u_3=5$ ; $u_n=F_{n+2}$, $u_{10}=144$ ; $c_{n,k}=\binom{n-k+1}{k}$ ; $56$