icone-challenge-math-OS

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\text{et}\qquad B_{2}=\left\{ 00,01,10\right\}\]

de sorte que :

    \[\beta_{1}=2\qquad\text{et}\qquad\beta_{2}=3\]

Pour tout n\geqslant3, classons les mots de longueur n ne comportant pas la séquence 11 en deux catégories :

  • l’ensemble Z_{n} de ceux commençant par 0 ,
  • l’ensemble U_{n} de ceux commençant par 1.

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 deB_{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}}\]

Petit rappel …

La suite de Fibonacci est définie par :

    \[F_{0}=0,\;F_{1}=1\qquad\text{et }\forall n\in\mathbb{N}^{\star},\thinspace F_{n+1}=F_{n}+F_{n-1}\]

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 détaillée 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\qquad\text{et}\qquad\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.

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

Or, par construction :

    \[f\circ g=id_{A_{n+1,2p+1}}\qquad\text{et}\qquad g\circ f=id_{C_{n,p}}\]

ce qui prouve que f est une bijection.

Il s’ensuit que \text{card}\left(C_{n,p}\right)=\text{card}\left(A_{n+1,2p+1}\right), c’est-à-dire :

    \[\boxed{\gamma_{n,p}=\binom{n+1}{2p+1}}\]


Pour consulter l’énoncé, c’est ici

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire