Palindrome bien parenthésé

Tu comptes comment tu peux dessiner les parenthèses à gauche, le reste à droite n’en est que le symétrique.

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.

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

Aléa, tu as fait une symétrie sur la grille par rapport aux autres solutions déjà donné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.

OK, j'ai capté. Si tu avais juste écrit "En supprimant le premier pas de la marche", j'aurais capté plus vite. ;-)

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.

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

Citation de GaBuZoMeu extraite de ce message (qui d'ailleurs t'était destiné) :

GaBuZoMeu a écrit:

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.

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.