Solution pour le challenge n° 50

Solution pour le challenge 50

Question 1

Notons $A_{n,p}$ l’ensemble des mots binaires de longueur $n$ comportant $p$ fois le symbole 1.

Imaginons un casier, composé de $n$ cases vides. Construire un élément de $A_{n,p}$ consiste à répartir dans le casier $p$ symboles 1 et $n-p$ symboles 0.

Le nombre de possibilités est donc égal au nombre de façons de choisir $p$ cases parmi $n$ (celles destinées à accueillir le symbole 1).

Ainsi, en posant $\alpha_{n,p}=\text{card}\left(A_{n,p}\right)$ :

$\boxed{\alpha_{n,p}=\binom{n}{p}}$

Question 2

Notons $B_{n}$ l’ensemble des mots binaires de longueur $n,$ ne comportant pas deux 1 consécutifs.

Notons $\beta_{n}=\text{card}\left(B_{n}\right).$ Clairement :

$B_{1}=\left\{ 0,1\right\}\qquad B_{2}=\left\{ 00,01,10\right\}$

de sorte que :

$\beta_{1}=2\qquad\beta_{2}=3$

Classons les mots de longueur $n\geqslant3$ ne comportant pas la séquence 11 en deux catégories :

ceux commençant par 0 : ils forment un sous-ensemble noté $Z_{n}$ .
ceux commençant par 1 : ils forment un sous-ensemble noté $U_{n}$

Les éléments de $Z_n$ sont obtenus en préfixant par 0 ceux de $B_{n-1}$ .

Les éléments de $U_n$ sont obtenus en préfixant par 10 ceux de $B_{n-2}$ .

En outre $B_{n}=Z_{n}\sqcup U_{n}$ (union disjointe). En passant aux cardinaux, on en déduit :

$\beta_{n}=\beta_{n-1}+\beta_{n-2}$

Les entiers $\beta_{n}$ sont donc les nombres de Fibonacci, mais avec un décalage de deux rangs, puisque $\beta_{1}=F_{3}$ et $\beta_{2}=F_{4}.$

Finalement, pour tout $n\geqslant1$ :

$\boxed{\beta_{n}=F_{n+2}}$

Question 3

Les choses se compliquent …

Notons $C_{n,p}$ l’ensemble des mots binaires de longueur $n$ comportant $p$ fois la séquence 01 et posons $\gamma_{n,p}=\text{card}\left(C_{n,p}\right).$

Commençons par déterminer $\gamma_{n,0},$ c’est-à-dire le nombre de mots binaires de longueur $n$ ne comportant pas la séquence 01.

Un tel mot doit être composé, pour un certain $k\in\left\llbracket 0,n\right\rrbracket ,$ de $k$ symboles 1 suivis de $n-k$ symboles 0 (justification ci-dessous). Par conséquent :

$\boxed{\gamma_{n,0}=n+1}$

Détail (cliquer pour déplier / replier)

Notons $\ell_{0},\cdots,\ell_{n-1}$ les lettres d’un mot binaire de longueur $n\geqslant2,$ ne comportant pas la séquence 01 et supposons l’existence d’un couple $\left(r,s\right)\in\left\llbracket 0,n-1\right\rrbracket ^{2}$ tel que $r<s,$ $\ell_{r}=0$ et $\ell_{s}=1.$ Soient alors : $u=\max\left\{ i\in\left\llbracket 0,n-1\right\rrbracket ;\thinspace\ell_{i}=0\text{ et }\exists j>i,\thinspace\ell_{j}=1\right\}$
et
$w=\min\left\{ j\in\left\llbracket u+1,n-1\right\rrbracket ;\thinspace\ell_{j}=1\right\}$

En clair :

$\ell_{u}$ est le 0 le plus à droite tel qu’il existe un 1 à droite de cette position (pas forcément juste après),
$\ell_{w}$ est le 1 le plus à gauche parmi les 1 situés à droite de $\ell_{u}.$

Supposons un instant que $w>u+1$ et considérons un entier $v$ tel que $u<v<w.$ On ne peut avoir ni $\ell_{v}=0$ (par définition de $u$ ) ni $\ell_{v}=1$ (par définition de $w)$ . Donc $w=u+1,$ ce qui montre la présence de la séquence 01, contrairement à l’hypothèse.

On a montré par l’absurde que, dans un mot de longueur $n\geqslant2$ ne comportant pas la séquence 01, on ne peut pas trouver un 0 suivi plus loin d’un 1. Ce mot est donc formé d’une séquence (éventuellement vide) de 1, suivie d’une séquence (éventuellement vide) de 0.

Nous allons établir une bijection entre les ensembles $C_{n,p}$ et $A_{n+1,2p+1}$ (notation de la question 1).

Etant donné $X=\left(x_{i}\right)_{1\leqslant i\leqslant n}\in C_{n,p},$ préfixons ce mot par 1 et suffixons-le par 0.

A partir du mot $Y=\left(y_{i}\right)_{0\leqslant i\leqslant n+1}$ obtenu (qui est de longueur $n+2),$ construisons un mot $Z=\left(z_{i}\right)_{0\leqslant i\leqslant n}$ de longueur $n+1$ comme suit :

$\forall i\in\left\llbracket 0,n\right\rrbracket ,\thinspace z_{i}=\left\{ \begin{array}{cc}0 & \text{si }y_{i}=y_{i+1}\\1 & \text{sinon}\end{array}\right.$

➡ Ceci définit une application $f:C_{n,p}\rightarrow A_{n+1,2p+1}.$

Par exemple, en partant de :

on forme successivement le mot :

puis le mot :

Inversement, considérons un mot $Z=\left(z_{i}\right)_{0\leqslant i\leqslant n}\in A_{n+1,2p+1}$ et construisons un mot $Y=\left(y_{i}\right)_{0\leqslant i\leqslant n+1}$ de longueur $n+2$ de la manière suivante :
$y_{0}=1$
et
$\forall i\in\left\llbracket 1,n+1\right\rrbracket ,\thinspace y_{i}=\left\{ \begin{array}{cc}y_{i-1} & \text{si }z_{i-1}=0\\1-y_{i-1} & \text{sinon}\end{array}\right.$

Comme $Z$ comporte un nombre impair de 1, on aura un nombre impairs de « changements » dans $Y$ (un changement est la transition d’un 0 vers un 1 ou inversement) et en particulier $y_{n+1}=0.$

Ensuite, supprimons le 1 en tête de $Y$ et le 0 en queue, autrement dit posons $X=\left(x_{i}\right)_{1\leqslant i\leqslant n}$ avec :

$\forall i\in\left\llbracket 1,n\right\rrbracket ,\thinspace x_{i}=y_{i}$

Le mot $X$ est de longueur $n$ et comporte $p$ fois la séquence 01 : en effet, comme $Y$ commence par un 1, le premier changement produit la séquence séquence 10 et il reste ensuite $2p$ changements : la moitié d’entre-eux donnent la séquence 01.