Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
42 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Palindrome bien parenthésé

Envoyé par pourexemple 
Palindrome bien parenthésé
il y a deux années
avatar
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.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par jacquot.
Re: Palindrome bien parenthésé
il y a deux années
${100\choose 50}=100891344545564193334812497256$.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Comment les as-tu compté ?

(Avec un calcul auquel tu sais donner un sens).
Re: Palindrome bien parenthésé
il y a deux années
avatar
En effet le résultat n'est pas difficile à conjecturer, mais justifier cette formule est autrement plus difficile...

On n'est, donc, pas dans un schéma associatif, donc les matrices (types Markov) ne suffiraient pas.



Edité 2 fois. La dernière correction date de il y a deux années et a été effectuée par pourexemple.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Tu comptes comment tu peux dessiner les parenthèses à gauche, le reste à droite n’en est que le symétrique.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: Palindrome bien parenthésé
il y a deux années
Il peut très bien n'y avoir que des parenthèses ouvrantes à gauche.
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é.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Ok, comment on fait (en donnant du sens au calcul effectué, sans cela la réponse de Jandri serait suffisante) ?
Re: Palindrome bien parenthésé
il y a deux années
Le nombre $u_n$ de palindromes bien parenthésés contenant exactement $2n$ parenthèses est égal au nombre de chemins croissants de longueur $n$, partant de 0 et vérifiant la condition $y\leq x$.
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}$.
Re: Palindrome bien parenthésé
il y a deux années
J'ai indiqué le moyen (qui ne me satisfait pas pleinement, je pense qu'il y a plus simple).
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.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par GaBuZoMeu.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Un lien vers ce principe de Symétrie de Désiré André.

Merci.
Re: Palindrome bien parenthésé
il y a deux années
avatar
@Jandri : Bravo.
Re: Palindrome bien parenthésé
il y a deux années
On attend toujours ta méthode de comptage (mais je sais d'expérience qu'on risque d'attendre longtemps).
Re: Palindrome bien parenthésé
il y a deux années
avatar
C'est Jandri qui a tombé le problème, s'il veut la connaître, qu'il s'exprime, sinon il peut estimer que cela ne lui apporterait rien de plus.

Il y a une différence, entre, être une éternelle insatisfaite, et ne pas donner réponse du tout.
Re: Palindrome bien parenthésé
il y a deux années
D'accord, c'est une question que tu as posée sans connaître le moyen de la résoudre. Je suis toujours à la recherche d'une bijection astucieuse qui rende clair le fait qu'on choisisse $\left\lfloor \dfrac{n}2\right\rfloor$ parmi $n$, plutôt que l'utilisation du principe de symétrie et la somme téléscopique, mais ce n'est donc pas toi qui me la donneras.



Edité 2 fois. La dernière correction date de il y a deux années et a été effectuée par jacquot.
Re: Palindrome bien parenthésé
il y a deux années
Bon, ce n'est pas grave, j'ai trouvé une bijection qui fait le boulot. Je traite juste le cas $n=2k$. C'est une bijection entre
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}}$.
Re: Palindrome bien parenthésé
il y a deux années
J'illustre la bijection, mais dans le cas $n=2k+1$. On transforme alors un chemin qui arrive en $(k+1,k)$ en un chemin de $2k+1$ pas qui reste sous la diagonale. Le dessin peut aussi donner l'idée de la description de la bijection réciproque.

PS. Le palindrome est (()(((())))()).



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par GaBuZoMeu.


Re: Palindrome bien parenthésé
il y a deux années
avatar
Ma chère GaBuZoMeu,

Citation
GaBuZoMeu
D'accord, c'est une question que tu as posée sans connaître le moyen de la résoudre.

Je te sens bien catégorique, je te conseille de bien réfléchir pour ne pas reproduire cette erreur.

Au revoir.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par pourexemple.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Une piste: on doit compter les marches de longueur $n$ qui restent positives.
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.
Re: Palindrome bien parenthésé
il y a deux années
Aléa, tu as fait une symétrie sur la grille par rapport aux autres solutions déjà données.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Je ne comprends pas bien ce que tu veux dire. La première ligne que j'écris est la traduction exacte de ton premier message; il n'y a pas de nouvelle idée.
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.
Re: Palindrome bien parenthésé
il y a deux années
Je parle de la représentation "graphique" des chemins. Jandri et moi présentons les chemins allant vers la droite et vers le haut sur une grille disposée "normalement" (comme les carreaux d'une feuille de cahier) et nous parlons de chemins sous la diagonale.
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.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Si tu notes $B_{n,\ell}$ le nombre de chemins de longueur $n$ partant de $0$ et ne passant pas en dessous de $-\ell$, tu as la récurrence
$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.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par aléa.
Re: Palindrome bien parenthésé
il y a deux années
OK, j'ai capté. Si tu avais juste écrit "En supprimant le premier pas de la marche", j'aurais capté plus vite. winking smiley
Re: Palindrome bien parenthésé
il y a deux années
avatar
Salut,

Citation
Aléa
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.
Re: Palindrome bien parenthésé
il y a deux années
Bon, ce que raconte pourexemple ne va pas, mais il y a tout de même une idée dedans. Reprenons cette idée de manière correcte. Je reprends aussi le formalisme d'alea.
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.



Edité 1 fois. La derni&egrave;re correction date de il y a deux ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par GaBuZoMeu.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Voleuse !

Ce n'est pas correct de s'attribuer les idées des autres, en ne faisant que les paraphraser...



Edité 1 fois. La derni&egrave;re correction date de il y a deux ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par pourexemple.
Re: Palindrome bien parenthésé
il y a deux années
Ça n'a rien à voir avec le schmilblick mais il me semble que GaBuZoMeu est un homme, je ne sais pourquoi tu t'adresses à lui au féminin.
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.
Re: Palindrome bien parenthésé
il y a deux années
avatar
1/ Si GaBuZoMeu, me dit qu'elle est un homme, alors je prendrais acte, sans cela je continuerais à parler d'elle au féminin.

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.
Re: Palindrome bien parenthésé
il y a deux années
Citation de GaBuZoMeu extraite de ce message (qui d'ailleurs t'était destiné) :

Citation
GaBuZoMeu
Désolé, il y avait des coquilles qui empêchaient peut-être ta compréhension. Je les ai corrigées.

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.
Re: Palindrome bien parenthésé
il y a deux années
Dans le dernier message de GaBuZoMeu, pour le 2), je pense que ce sont les marches qui descendent au niveau $2k-n+1$ et pas $2k-n-1$.
Re: Palindrome bien parenthésé
il y a deux années
Oui bien sûr tu as raison Jandri, on ne va pas descendre au niveau $-n-1$ avec une marche de $n$ pas ! Je corrige.
Re: Palindrome bien parenthésé
il y a deux années
avatar
Pas très grave, car je suis satisfait que tout cela découle des messages d'Aléa (comme elle le reconnait elle même), et donc la paternité lui revient de plein droit.

Ensuite pour ce qui de l'usage du féminin pour notre amie : [www.les-mathematiques.net]

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.



Edité 1 fois. La derni&egrave;re correction date de il y a deux ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 136 345, Messages: 1 318 049, Utilisateurs: 24 023.
Notre dernier utilisateur inscrit Etienne l’autre.


Ce forum
Discussions: 735, Messages: 5 965.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page