Nombre de Schröder

En mathématiques, et notamment en combinatoire, les nombres de Schröder forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement.

Le nombre de Schröder ${\displaystyle r_{n}}$dénombre les chemins dans une grille de taille ${\displaystyle n\times n}$ reliant le point de coordonnées (0, 0) au point de coordonnées ${\displaystyle (n,n)}$ en utilisant seulement des pas unités de direction nord, nord-est ou est, et qui ne dépassent pas la diagonale sud-ouest - nord-est. Un tel chemin est appelé un chemin de Schröder.

Les premiers nombres de Schröder, en commençant à ${\displaystyle n=0}$ sont :

1, 2, 6, 22, 90, 394, 1806, 8558, .... (C'est la suite A006318 de l'OEIS).

Ils sont nommés ainsi en référence au mathématicien allemand Ernst Schröder^[1]. Ils sont proches des nombres de Catalan (qui dénombrent ceux parmi les chemins de Schröder qui ne comportent pas de pas de direction nord-est), des nombres de Motzkin, et des nombres de Schröder-Hipparque. Comme eux, ils possèdent de nombreuses interprétations combinatoires^[2].

Les nombres de Schröder comptent le nombre de chemins de (0, 0) à ${\displaystyle (2n,0)}$, formés de pas unitaires nord-est et sud-est (pas (1, 1) ou (1, –1)) ou de pas horizontaux doubles (pas (2, 0)), et qui sont de plus toujours au-dessus de l'axe des ${\displaystyle x}$. Ils ressemblent en cela aux chemins de Motzkin, sauf qu'ici, les pas horizontaux viennent par deux.

Le n-ème nombre de Schröder compte aussi le nombre de subdivisions d'un rectangle en ${\displaystyle n+1}$ rectangles plus petits obtenu par ${\displaystyle n}$ segments horizontaux ou verticaux, avec la restriction qu'il y a ${\displaystyle n}$ points à l'intérieur du rectangle qui ne sont alignés ni horizontalement ni verticalement, et que tout segment passe par un des points et ne divise qu'un seul rectangle en deux. Sur la figure ci-dessous figurent les 6 subdivisions rectangulaires (rectangulations) en 3 rectangles avec 2 segments^[3].

Une parmi les autres caractérisations données dans  A006318 lie les nombres de Schröder aux chemins de Motzkin : le n-ème nombre de Schröder est le nombre de chemins de Motzkin colorés de longueur ${\displaystyle n}$ où chaque pas montant ou horizontal au niveau de l’axe a une parmi deux couleurs, et chaque autre pas horizontal une parmi trois couleurs : pour ${\displaystyle n=2}$, on a les 6 possibilités suivantes, où la couleur est notée juste après le pas : U1D, U2D, H1H1, H1H2, H2H1, H2H2. Ici, tous les pas horizontaux sont au niveau de l'axe.

Langage formel. On peut associer à chaque chemin de Schröder un mot sur l'alphabet ${\displaystyle \{y,x,{\bar {x}}\}}$, en codant par ${\displaystyle y}$ un pas horizontal, par ${\displaystyle x}$ un pas montant et par ${\displaystyle {\bar {x}}}$ un pas descendant^[4]. Ainsi, les 6 mots de longueur 4 sont

${\displaystyle yyyy,yyx{\bar {x}},x{\bar {x}}yy,xyy{\bar {x}},x{\bar {x}}x{\bar {x}},xx{\bar {x}}{\bar {x}}}$.

L'ensemble de ces mots est le langage de Schröder ${\displaystyle R}$. Il est donné par la grammaire formelle ou équation :

${\displaystyle R=1+yyR+xR{\bar {x}}R}$

Les mots de longueur ${\displaystyle 2n}$ sont comptés par le nombre de Schröder ${\displaystyle r_{n}}$.

Les nombres de Schröder valent, à l'exception du premier, le double des petits nombres de Schröder ou nombres de Schröder-Hipparque.

Formule de récurrence forte. Partant de ${\displaystyle r_{0}=1}$, la suite ${\displaystyle (r_{n})}$ peut être définie par la relation de récurrence ,

${\displaystyle r_{n}=r_{n-1}+\sum _{k=0}^{n-1}r_{k}r_{n-1-k}}$.

On peut voir cette formule comme suit : un chemin horizontal de longueur ${\displaystyle 2n}$ commence soit par deux pas horizontaux suivis d'un chemin de longueur ${\displaystyle 2(n-1)}$, soit commence par un pas diagonal. Dans ce cas, lorsque le chemin touche pour la première fois l'axe des ${\displaystyle x}$, on a délimité un chemin horizontal de Schröder partant de (1,1), de longueur ${\displaystyle 2k}$, avec ${\displaystyle 0\leqslant k\leqslant n-1}$.

Formule de récurrence double. Partant de ${\displaystyle r_{0}=1,r_{1}=2}$, la suite ${\displaystyle (r_{n})}$ peut être définie par la relation de récurrence^[5] :

${\displaystyle r_{n}={\frac {1}{n+1}}{\Big (}(6n-3)r_{n-1}-(n-2)r_{n-2}{\Big )}.}$.

Série génératrice. Soit

${\displaystyle r(x)=r_{0}+r_{1}x+\cdots +r_{n}x^{n}+\cdots =1+2x+6x^{2}+22x^{3}+90x^{4}+\cdots }$

la série génératrice des nombres de Schröder. Elle satisfait l'équation^[6] suivante :

${\displaystyle r(x)=1+xr(x)+xr(x)^{2}}$.

On obtient l'expression close :

${\displaystyle r(x)={\frac {1-x-{\sqrt {1-6x+x^{2}}}}{2x}}}$.

Formule close. On a^[4] : ${\displaystyle r_{n}=\sum _{i=0}^{n}{\binom {2n-i}{i}}C_{n-i}}$ où ${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}}$ est le nombre de Catalan d'indice ${\displaystyle n}$.

Comportement asymptotique. L'étude de la série génératrice permet d'obtenir^[6] :

${\displaystyle r_{n}\sim {\frac {1}{2{\sqrt {\pi n^{3}}}}}(3-2{\sqrt {2}})^{-n-1/2}}$.

• Nombre de Delannoy
• Nombre de Motzkin
• Nombre de Narayana
• Nombre de Schröder-Hipparque

• (en) Eric W. Weisstein, « Schröder Number », sur MathWorld
• (en) Richard P. Stanley, « Catalan addendum », sur www-math.mit.edu, Information on Enumerative Combinatorics, 1999 (consulté le 3 décembre 2013) Complément sur les nombres de Catalan à son livre Enumerative Combinatorics, Volume 2.

• Portail des mathématiques