Dénombrement de mots — Les-mathematiques.net The most powerful custom community solution in the world

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.

Réponses

  • Bonjour,

    $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...
  • La formule est bonne, en revanche je ne connais pas de solution directe, seulement passant par le calcul et les marches aléatoires.

    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$.
  • @ aléa : la méthode que je suggère n'est pas selon toi " directe "? tu veux que je la précise?
  • @lesmathspointclaires
    Oui, ça m'intéresse. Merci.
  • Il est clair que $C_{2n}^n$ est le nombre de mots "equilibrés" avec autant de $a$ que de $b$, on va associer à chaque mot équilibré $e$ un mot $A(e)$ qui est a-dominant (c'est ainsi que je qualifie les mots dont tout segment initial contient plus de a que de b , dont on veut montrer qu'il y en a $C_{2n}^n$)

    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...
  • Tu m'as perdu dès la première ligne: la condition de Fontana me semble différente de la tienne.

    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$).
  • Il y a une petite erreur.... je la corrige
  • aléa , d'accord^^ c'est pour ça que je buttais...
  • Je confirme ça demain mais il semble que switcher tout le monde à partir du moment où on va atteindre 0 et faire de même avec le tronçon switché (en ignorant les tronçons précédents) donne le bon a-dom associé) Je serai plus précis... mais je ne suis pas encore certain que ça marche...
  • Ça y est c'est assez simple à voir comme ça :

    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
  • Les "blocs" sont - à une lettre près correspondant à la couleur - les seuls objets à être dans les deux types de mots! Il sont des sortes d'irreductibles pour les deux types de mots, dont la décomposition la plus naturelle qu'on puisse imaginer ne nécessite que l'ajout des deux couleurs pour être caractérisante.
  • Bonjour
    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.
  • Ne s'agit-il pas plutôt de Catalan ?
  • Oui il s'agit en effet des nombres de Catalan qui vérifient : $C_n = \frac{1} {n+1} \binom{2n}{n}$
  • Quelque chose n'est pas clair dans l'algo canonique que j'ai donné ?? (pour passer de a-dom (dominé commençant par a) à a-équilibrés (autant de a que de b et commençant par a))



    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 vais l'ecrire formellement car je ne vois aucune réaction alors que le problème me semble résolu doublement puisqu'il donne un algo on ne peut plus canonique :

    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
  • @ alea et Fontana : pourquoi ce silence? Certes j'ai fait une petite faute de lecture d'énoncé, mais est-ce une raison pour ne plus rien lire ?


    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$
  • Bonjour,

    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 .}$
  • @LOU16 : Peut-être que quelque chose m'échappe, mais il me semble que tu déduis les coefficients de la série à partir de sa somme?(dernière ligne)
  • Re,
    @lesmathspointclaires
    En effet, les coefficients de la série $(1-4X)^{-\frac12}$ sont les $\binom {2n}n$.
  • Du coup il faut faire quelques calculs pénibles pour obtenir les coefs?
  • Re,

    @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$.
  • C'est un dénombrement qui peut se résoudre avec le principe de symétrie de Désiré André.

    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}$.
  • @LOU16 : Oui c'est vrai que tu as supposé connue cette égalité, mais pour l'obtenir, il faut faire un calcul pas compliqué mais tout de même pénible... c'est agréable de retomber sur ces pates, et c'est joli mais non seulement on fait appel à une théorie non élémentaire (comparée à l'élémentarité du problème et de la solution que je propose) mais en plus on fait des calculs. Dans une moindre mesure je fais le même reproche à la methode très jolie de Jandri, on voit mieux ce qui se passe mais elle demande un calcul qu'un enfant de 10 ans ne peut pas effectuer, même remarque encore pour la récurrence donnée plus haut par blasselle
    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!!
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!