Dénombrement de mots
Bonjour,
Je suis à la recherche de pistes concernant l'exercice suivant :
On considère $M$ l'ensemble des mots sur l'alphabet $\{a,b\}$ de longueur $2n$. Dénombrer le nombre de mots $w$ de $M$ tels que pour tout $k \in \{1,...,n\}$, le préfixe $w_1 \cdots w_{2k}$ ne contienne pas autant de $a$ que de $b$.
En testant de petites valeurs de $n$, j'ai l'impression qu'on peut conjecturer qu'on trouve $\binom{2n}{n}$, mais je ne vois pas trop de façon combinatoire de le voir.
Merci pour votre aide.
Je suis à la recherche de pistes concernant l'exercice suivant :
On considère $M$ l'ensemble des mots sur l'alphabet $\{a,b\}$ de longueur $2n$. Dénombrer le nombre de mots $w$ de $M$ tels que pour tout $k \in \{1,...,n\}$, le préfixe $w_1 \cdots w_{2k}$ ne contienne pas autant de $a$ que de $b$.
En testant de petites valeurs de $n$, j'ai l'impression qu'on peut conjecturer qu'on trouve $\binom{2n}{n}$, mais je ne vois pas trop de façon combinatoire de le voir.
Merci pour votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$C_{2n}^n$ est le nombre de mots qui contiennent autant de $a$ que de $b$ (sans autre condition), il ne reste plus qu'à associer à chacun d'eux un unique mot dont tu parles...
En effet, si on divise le nombre que tu cherches par $2^{2n}$, le résultat représente la probabilité qu'une marche aléatoire symétrique ne revienne pas à son point de départ entre les temps $1$ et $2n$.
Oui, ça m'intéresse. Merci.
Soit donc $e=e_1e_2...e_{2n}$ un mot equilibré, s'il est aussi a-dominant on lui associe lui même i.e $e=A(e)$ et si ce n'est pas le cas on prend pour $A(e)$, le mot a-dom le "plus proche" , i.e le mot a-dom qui a le plus de lettres identiques à la même place, et on le construit comme ceci à partir de $e$ : Soit le mot est déjà a-dom, et on ne fait plus rien. Sinon, dès qu'il y a strictement plus de $a$ que de $b$ dans un segment initial de $e$, disons au rang $r_1$, on change le dernier $b$ en $a$ et on obtient $f(e)$, notons que $e_1e_2...e_{r-1}$, segment initial de $f(e) $ est à la fois équilibré et a-dominant. Si c'est le cas de $f(e)$ tout entier, on arrête, on a notre a-dominant associé à $e$, sinon on reproduit l'opération sur $f(e)$ en obtenant $f(f(e))$ au rang $r_2>r_1$ et ainsi de suite. Le processus s'arrête à l'étape $j$. Et on a $j$ sous mots à la fois équilibrés et a-dominants concaténés, on observe aussi que le mot final associé à $e$ (qui vaut $f(f(f(....f(e)...))):=f^j(e):=A(e)$, a $n-j$ fois la lettre $b$ et $n+j$ foos la lettre $a$, il ne reste qu'à montrer que la fonction $A$ est bijective. Dans le prochain post...
Si $a=1$ et $b=-1$, je comprends l'énoncé comme pour tout $k\in\{1,\dots, 2n\}$, $w_1+\dots +w_k\ne 0$.
J'ai l'impression que ton interprétation est différente.
Tu as l'air de dire $w_1+\dots +w_k\le 0$ (ou $w_1+\dots +w_k< 0$).
Appelons "bloc" tout mot de somme nulle (autant de a que de b) tel que tout segment initial propre ne soit pas de somme nulle. Tout mot de somme nulle est une concaténation de blocs, dont chacun est soit un a-bloc (tout segment initial contient plus de a) soit un b-blocs
Quitte à colorier (rouge et bleu) les blocs en fonction de leur première lettre on peut se ramener à des a-blocs coloriés.
Prenons maintenant un mot tel que tout segment initial soit de somme non nulle (mot dominé)
regardons le plus grand segment initial qui soit de somme 1 ou -1, dans un cas on le colorie en bleu dans l'autre en rouge, on colorie la lettre suivante de la même couleur, et on la remplace par l'autre lettre, on obtient donc un bloc colorié.
S'il y a des blocs dans le mot suivant on les colorie de l'autre couleur.
On reproduit l'opération sur le segment final non encore colorié jusqu'a n'obtenir que des blocs coloriés.
On passe ainsi de mot de somme nulle a mot dominé et inversement
Si tu notes $(u_n)$ la suite que tu cherches alors on peut aisément montrer qu'elle vérifie la relation de récurrence : $u_{n+1} = 4u_n - 2 C_n$
où $C_n$ désigne le n-ième nombre de Catalan.
Une récurrence clôt ensuite facilement la démonstration.
Chaque étape transforme consécutivement des segments initiaux du a-dom en "blocs" qui ne varient plys une fois transformés (un bloc est un equilibré tel que tous ses segements initiaux sont non equilibrés)
On regarde le plus grand segment de somme 1, (la lettre d'après est un a qu'on switch en b, on a ainsi le premier "bloc") quant au mot qui "reste", on a que 2 possibilités:
1) ou bien aucun de ses segments initiaux n'est de somme nulle, et on se ramène à l'étape précédente
2) ou bien il y a un plus grand segment initial de somme nulle, et on inverse les a en b sur ce sous mot (on obtient donc des b-blocs)
On s'arrête quand on ne peut plus, c'est à dire quand il n'y a plus que des blocs !
Je note $+$ la concaténation
Pour tout (a,b)-mot $m$ , $S(m)$ est le nombre de $a$ moins le nombre de $b$
$|m|$ est le nombre de lettres de $m$
Pour tout $i\leq |m|$ , $m(i)$ est sa i-ème lettre, identifiee avec un mot de taille 1
$m[i,j]=m(i)+m(i+1)+...+m(i)$
$F$ est l'ensemble des mots de Fontana
$E$ l'ensemble des mot qui annulent $S$
$H$ l'ensemble des mots du type $e+f$ où $(e,f)\in E\ times F$
(mots hybride)
On définit :
$ gauche(h)=e$ et $droite(h)=f$
Pour un mot $m$ et $i\leq j\leq |m|$
$switch(m,i,j)$ est tel que $switch(m)(k)\ne m(k)$ ssi $k\in [i,j]$
A tout mot de Fontana $f\in F$ on associe un degrés, $d(f)= \max\left\{i \leq |f|, \, S(f[1,i])=S(f[1,1])\right\}$
$A(f)$ retourne $switch(f,d(f)+1,d(f)+1)$
(on switch la lettre juste après le rang du degré)
Pour tout mot hybride $h\in H$ on définit $B(h)= switch(gauche(h))+droite(h)$
Pour tout mot hybride $h$ on définit
$Etap(h)=gauche(h)+B(A(h))$
On note que
$Etap(h)=h$ ssi $h\in E$
$Etap^{k+1}(h) := Etap^k(Etap(h)$
$k\mapsto Etap^k(h)$ est stationnaire
La valeur stationnaire de cette suite est $ Result(h)$
La réstriction de result aux mots de Fontana donne une bijection de F sur E
La clé du raisonnement :
Un mot de Fontana f admet une unique décomposition en concaténation de mots de Fontana de somme 2 ou -2
Or, il y a une injection (B) entre les Fontana de somme 2 ou -2 et les mots de somme nulle : On switch toutes les lettres qui suivent le plus grand segment initial de somme 1 ou -1
Cette fonction B se prolonge à tous les mots de Fontana par la formule
B(f)= B(f_1) + B(f_2) + ... +B(f_i )
où les f_i sont des mots de Fontana de somme 2 ou -2 et + la concaténation
L'unicité de la décomposition des Fontana assure la bonne définition et l'injectivité du prolongement et pour la surjectivité, On ecrit un mot z de somme nulle comme $ z=z_1 + z_2$ de sorte
1) que si $z_1$ est concaténation de plusieurs mots de somme nulle, la première lettre du premier n'est pas la première lettre des suivants. [je viens d'éditer]
2) que $z_1$ soit maximal pour la propriété 1
$B^{-1}(z_1) $ ( bien défini) donne le premier segment initial maximal de somme 2 ou -2 de $ B^{-1}(z)$ et les autres s'obtiennent similairelent à partir de $z_2$
J'ai pour ma part aperçu un dénombrement qui induit un produit de séries formelles et utilise le fait que $\displaystyle \sum_{n=0}^{+\infty} \binom {2n}n X^n= \dfrac 1{\sqrt{1-4X}}$.
$\forall n \in \N^*, \quad W_n := \Big\{ w=(w_i)_{1\leqslant i \leqslant 2n} \:|\: \forall i \in [\![1;2n]\!], \: w_i \in \{-1,1\}\Big\},\quad \forall w \in W_n,\quad \alpha (w): = \max \Big\{ k \in [\![0;n]\!] \:|\: \displaystyle \sum_{i=1} ^{2k} w_i =0 \Big\}.$
$ \text{ Le nombre de mots cherché est}\:u_n:= \text{Card} \Big\{w\in W_n \:|\: \forall k \in [\![1;n]\!],\: \displaystyle \sum _{i=1} ^{2k} w_i \neq 0 \Big \}.$
Alors: $4^n = \text{Card}\;W_n= \displaystyle \sum _{k=0}^n \text{Card}\Big \{w\in W_n \:|\: \alpha(w) = k \Big\} =\sum_{k=0}^n \binom {2k}k u _{n-k}.\quad$ (avec la convention $u_0=1$)
En introduisant les séries formelles $\:S(X) =\displaystyle \sum_{n=0}^{+\infty}4^nX^n =\dfrac 1{1-4X}, \quad T(X)=\sum_{n=0}^{+\infty} \binom {2n}n X^n =\dfrac 1{\sqrt{1-4X}},\quad U(X)= \sum _{n=0}^{+\infty} u_n X^n,$
l'égalité précédente se traduit par $\:S(X) =T(X) U(X)$ qui entraine $U(X) = \dfrac 1{\sqrt {1-4X}}\:$ et $\quad \boxed{\forall n \in \N,\: u_n =\displaystyle\binom {2n}n .}$
@lesmathspointclaires
En effet, les coefficients de la série $(1-4X)^{-\frac12}$ sont les $\binom {2n}n$.
@mathspointclaires
Il s'agit d'appliquer ce que l'on nomme parfois "la formule du binôme généralisée", à savoir:
$(1-4X)^{-\frac12}= \displaystyle \sum _{n=0}^{+\infty} \binom{-\frac12}n (-4X)^n = \sum _{n=0}^{+\infty} \binom {2n}n X^n$, qui est l'identité que j'indiquais en introduction, que l'on peut lire comme une égalité de séries formelles (où $(1-4X)^{-\frac12} $ désigne l'unique série formelle $U(X)$ telle que $U(X)^2 =\dfrac1{1-4X}$ et $U(0)= 1$) ou bien une égalité entre des nombres réels, valable pour tout $X$ tel que $-1<4X<1$.
Le nombre recherché est égal à deux fois le nombre de chemins croissants de longueur $2n-1$, partant de $A(1,0)$ et ne rencontrant pas la première bissectrice. Un tel chemin se termine en un point $B_k(n+k,n-k)$ avec $1\leq k\leq n$.
L'astuce de Désiré André consiste à introduire le point $A'(0,1)$ et à associer bijectivement à un chemin allant de $A$ à $B_k$ et coupant pour la première fois la première bissectrice en $M$ le chemin allant de $A'$ à $B_k$ et coupant pour la première fois la première bissectrice en $M$ obtenu en symétrisant le chemin allant de $A$ à $M$.
Le nombre de chemins convenables allant de $A$ à $B_k$ est égal à $f(A,B_k)-f(A',B_k)$ où $f(A,B)$ désigne le nombre de chemins croissants allant de $A$ à $B$ (sans condition), donc égal à $\displaystyle{2n-1\choose n-k}-{2n-1\choose n-k-1}$.
On en déduit le résultat: $2\displaystyle\sum_{k=1}^n\left({2n-1\choose n-k}-{2n-1\choose n-k-1}\right)=2{2n-1\choose n-1}={2n\choose n}$.
Si vous examinez mon algorithme de conversion, il est très canonique et compréhensible par un enfant de 10 ans : pour reprendre la terminologie de jandri, on décompose le chemin en chemin en sous chemins convenables tel que k=1 en associant à ces chemins "irreductibles" un chemin qui ne traverse strictement qu'une seule fois au plus la bissectrice (voir détail plus haut) on a ZERO calcul!!