Dénombrement de mots

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$.

@lesmathspointclaires
Oui, ça m'intéresse. Merci.

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$).

aléa , d'accord^^ c'est pour ça que je buttais...

Ç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

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.

Oui il s'agit en effet des nombres de Catalan qui vérifient : $C_n = \frac{1} {n+1} \binom{2n}{n}$

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

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 .}$

Re,
@lesmathspointclaires
En effet, les coefficients de la série $(1-4X)^{-\frac12}$ sont les $\binom {2n}n$.

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$.

@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!!