Palindrome bien parenthésé
Salut,
Combien y-a-t-il de palindromes bien parenthésés, contenant exactement 200 parenthèses ?
On détaillera la technique de comptage utiliser.
PS : à la taille 8 on a par exemple (((()))) et (())()() n'est pas un palindrome.
Cordialement.
Combien y-a-t-il de palindromes bien parenthésés, contenant exactement 200 parenthèses ?
On détaillera la technique de comptage utiliser.
PS : à la taille 8 on a par exemple (((()))) et (())()() n'est pas un palindrome.
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
(Avec un calcul auquel tu sais donner un sens).
On n'est, donc, pas dans un schéma associatif, donc les matrices (types Markov) ne suffiraient pas.
-- Schnoebelen, Philippe
Par contre, il ne peut pas y avoir n'importe quoi (par exemple, pas uniquement des parenthèses fermantes à gauche.
Ce qui est vrai, c'est qu'il suffit de fixer les 100 premières parenthèses, de telle façon que tout segment commençant de l'arrangement de parenthèses comporte au moins autant d'ouvrantes que de fermantes. Le décompte peut se faire à l'aide du principe de symétrie de Désiré André.
Pour les dénombrer je note $v_{n,k}$ le nombre de chemins croissants joignant 0 au point $M_k(n-k,k)$.
En utilisant le principe de symétrie de Désiré André on obtient $v_{n,k}={n\choose k}-{n\choose k-1}$ (nombre de chemins de 0 à $M_k$ moins le nombre de chemins de $A(-1,1)$ à $M_k$).
On en déduit $u_n=1+\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}v_{n,k}={n\choose \lfloor n/2\rfloor}$.
Et si tu nous disais comment tu fais (si jamais tu sais faire) ?
PS. Bon, Jandri a vendu la mèche en utilisant le même moyen que celui que j'indiquais.
Merci.
Il y a une différence, entre, être une éternelle insatisfaite, et ne pas donner réponse du tout.
1) l'ensemble des chemins de $(0,0)$ à $(k,k)$ par $k$ pas de $1$ vers la droite et $k$ pas de $1$ vers le haut (dans l'ordre qu'on veut)
et
2) l'ensemble des chemins de $n=2k$ pas de $1$ soit vers la droite, soit vers le haut, qui ne passent pas au-dessus de la diagonale $y=x$. (Ce dernier ensemble est bien celui que l'on veut dénombrer, il correspond à la première moitié du palindrome avec les pas vers la droite correspondant aux parenthèses ouvrantes et les pas vers le haut aux fermantes.)
La bijection de 1) vers 2) fonctionne ainsi :
On part d'un chemin de 1). Le premier pas vers le haut qui arrive à la droite $y=x+1$, on le transforme en pas vers la droite. Le premier pas vers le haut qui arrive à la droite $y=x+2$, on le transforme en pas vers la droite. Et ainsi de suite. Si le chemin montait jusqu'à la droite $y=x+\ell$ et pas plus haut, le chemin transformé ne passe pas au-dessus de la diagonale et arrive en $(k+\ell, k-\ell)$.
Je laisse à la lectrice assidue la démonstration qu'il s'agit bien d'une bijection (ce qui peut se faire par la description de l'application réciproque).
La bijection entre 1) et 2) montre que le cardinal de 1) est bien égal à $\displaystyle{\binom{2k}{k}}$.
PS. Le palindrome est (()(((())))()).
Je te sens bien catégorique, je te conseille de bien réfléchir pour ne pas reproduire cette erreur.
Au revoir.
Si j'introduit les marches de longueur $n$ qui restent au dessus de $-\ell$, j'obtiens une récurrence double qui ressemble au triangle de Pascal.
Mais la piste que je propose avec la récurrence double ne contient aucune idée de principe de symétrie de type André.
Note, je ne sais pas si ça marche.
Tu présentes les chemins comme les graphes d'une fonction linéaire par morceaux de pente $1$ ou $-1$ et tu parles de chemins restant positifs.
C'est juste un changement cosmétique, on passe d'une représentation à l'autre par une symétrie. C'est tout ce que je disais. Ta façon de dessiner est plus habituelle chez les probabilistes ?
Sinon, pour la piste que tu proposes, j'avoue que je ne vois pas encore très bien la récurrence double.
$B_{n,\ell}=B_{n-1,\ell-1}+B_{n-1,\ell+1}$, et pleins de conditions aux bords.
Je ne sais pas où ça mène, mais ça semble une approche bien naturelle.
Bravo, c'est à peu de chose prés, le moyen que j'avais utilisé.
On prend le polynôme
$P_0=1$
On calcule
$P_{n+1}=(P_n \times (X+Y) \mod (X\times Y-1)) \mod Y$
$P_{100}(1)$ donne la solution.
Cordialement.
On travaille avec les polynômes de Laurent à coefficients entiers, c.-à-d. dans $\Z[X, X^{-1}]$. Soit $P_n=(X+X^{-1})^n$. Alors
1°) Pour tout entier $k$ tel que $0\leq 2k <n$, le nombre de marches de longueur $n$ qui descendent au niveau $2k-n$ sans descendre en-dessous est le coefficient de $X^{2k-n}$ dans $P_n$.
2°) Pour tout entier $k$ tel que $0\leq 2k < n-1$, le nombre de marches de longueur $n$ qui descendent au niveau $2k-(n-1)$ [edit : correction de coquille signalée par Jandri] sans descendre au-dessous est le coefficient de $X^{n-2k}$ dans $P_n$.
3°) Le nombre de marches de longueur $n$ positives ou nulles est le terme constant de $P_n$ si $n$ est pair, et le coefficient de $X$ si $n$ est impair.
Ce n'est pas correct de s'attribuer les idées des autres, en ne faisant que les paraphraser...
Je ne sais pas non plus pourquoi tu es si désagréable avec lui. Tu devrais lui être reconnaissant de s'intéresser à tes questions, d'avoir compris l'idée qui se cachait derrière ton charabia faux et d'en avoir fait quelque-chose de juste.
2/ Je n'ai pas besoin de sa pitié ni de celle d'une autre, si elle ne trouve aucun intérêt à mes idées, inutile de faire dans l'humanitaire et d'y répondre, ou de les paraphraser en faisant mine de dire autre chose que ce que j'ai déjà dit, tout cela pour s'attribuer une idée qu'un autre a eut à sa place.
Au revoir.
Quand on écrit "désolé", c'est qu'on est un homme, une femme écrit "désolée".
Je répète que tu es très agressif avec lui et que contrairement à ce que tu dis, il n'a pas "fait mine de dire autre chose", mais a bien dit autre chose. Si tu n'es pas capable de le voir, soit tu ne sais pas lire le français, soit tu ne comprends pas les maths.
T'inquiète pas je ne viendrai plus t'embêter.
Au revoir, donc.
Ensuite pour ce qui de l'usage du féminin pour notre amie : http://www.les-mathematiques.net/phorum/read.php?43,1198849,1376136#msg-1376136
Il suffit qu'elle me dise, que cela la gêne, et alors, je stoppe net, sans cela je ne vois pas de mal à être une femme, sauf quand on n'en est pas une.
Au revoir.