Nombre de Schröder-Hipparque

Les $s_3=11$ subdivisions d'un pentagone.

En mathématiques, et notamment en combinatoire, les nombres de Schröder-Hipparque forment une suite d'entiers dénombrant :

- les arbres planaires ayant un ensemble donné de feuilles,

- les insertions de parenthèses dans un mot,

- les façons de découper un polygone convexe en polygones plus petits par l'insertion de diagonales.

Les dix premiers nombres de Schröder-Hipparque (pour Modèle:Mvar de 0 à 9) sont :

$\begin{array}{ccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ s_n& 1& 1& 3& 11& 45& 197& 903& 4279& 20793& 103049\end{array}$ voir la Modèle:OEIS.

Ces nombres sont aussi appelés super-nombres de Catalan, petits nombres de Schröder, ou nombres d'Hipparque, en référence à Eugène Charles Catalan et ses nombres de Catalan, à Ernst Schröder et ses (grands) nombres de Schröder très voisins, et au mathématicien et astronome grec Hipparque qui, selon Plutarque, connaissait certainement ces nombres.

Applications en combinatoire énumérative

Équivalence combinatoire entre subdivisions de polygones, arbres enracinés et parenthésages. Le mot est (ab(cdef))g.

Les $s_2=3$ subdivisions du carré, les 3 arbres, et les 3 parenthésages correspondants.

Les nombres de Schröder-Hipparque dénombrent des objets combinatoires dont on sait par ailleurs qu'ils sont étroitement reliés entre eux Modèle:,Modèle:,Modèle:, :

• Le n-ième nombre de la suite (soit $s_{n-1}$) est le nombre de subdivisions d'un polygone à $n+1$ côtés en polygones plus petits par l'adjonction de diagonales au polygone de départ.
• Le n-ième nombre est le nombre d'arbres enracinés à $n$ feuilles dont les nœuds internes ont au moins deux enfants.
• Le n-ième nombre est aussi le nombre de façons d'insérer des parenthèses dans une suite de $n$ symboles, de sorte que toute paire de parenthèses entoure au moins deux symboles ou groupes parenthésés, et sans paire de parenthèses entourant la suite tout entière.
• Le n-ième nombre donne enfin aussi le nombre de faces, de toute dimension, d'un associaèdre $K_{n+1}$, de dimension $n-1$, y compris l'associaèdre lui-même vu comme une face, mais sans compter l'ensemble vide. Par exemple, l'associaèdre K₄, de dimension 2, est un pentagone; il a cinq sommets et cinq arêtes, ce qui donne, avec l'associaèdre lui-même, un total de 11 faces.

La figure illustre la bijection combinatoire simple entre ces objets : une subdivision d'un polygone est représenté par un arbre planaire qui est son graphe dual. Les feuilles de l'arbre sont en bijection avec les symboles de la suite représentée, et les nœuds internes, à l'exception de la racine, représentent des groupes parenthésés. La suite des parenthèses elle-même peut s'inscrire sur le contour du polygone : les symboles sont sur les côtés et les parenthèses délimitent les extrémités des diagonales : la parenthèse est ouvrante à la première rencontre, et fermante à la deuxième. Cette équivalence donne une preuve par bijection du fait que tous ces objets sont dénombrés par une même suite d'entiers.

La même suite dénombre aussi les permutations doubles (ce sont des suites finies d'entiers de 1 à $n$ où chaque nombre apparaît deux fois, les premières occurrences de chaque nombre étant en ordre croissant) qui évitent les motifs 12312 et 121323.

D'autres interprétations sont données dans Modèle:Harvsp.

Suites voisines

• Les nombres de Schröder ou grands nombres de Schröder valent, à l'exception du premier, le double des nombres de Schröder-Hipparque, et dénombrent divers types d'objets combinatoires parmi lesquels certaines familles de chemins dans des grilles, les partitions de rectangles en rectangles plus petits par des découpes en tranches verticales ou horizontales, des parenthésages où on autorise aussi une paire de parenthèses autour de la suite entière.
• Les nombres de Catalan dénombrent des ensembles similaires d'objets, parmi lesquels les triangulations de polygones convexes, les arbres binaires (dont les nœuds internes ont exactement deux enfants), ou les parenthésages dans lesquels toute paire de parenthèses entoure exactement deux symboles ou groupes parenthésés.
• On peut faire un parallèle entre les associaèdres et les Modèle:Lien : les nombres de Schröder-Hipparque dénombrent les faces et les nombres de Catalan les sommets d'un associaèdre ; les nombres correspondants pour les permutoèdres sont les nombres de Bell ordonnés et les factorielles.

Expression

La suite des nombres de Catalan et celle des nombres de Schröder-Hipparque peuvent être vues comme des vecteurs. Ce sont alors les seuls vecteurs propres pour les deux premiers opérateurs d'une famille d'opérateurs linéaires sur les suites d'entiersModèle:,. La k-ième suite de cette famille de suites d'entiers est la suite

$x_1,x_2,\dots ,x_n,\dots$

où les $x_n$ sont obtenus comme sommes de nombres de Narayana multipliés par des puissances de $k$ :

$x_n=\sum _{i=1}^{n}N(n,i)k^{i-1}=\sum _{i=1}^n\frac{1}{n}(\genfrac{}{}{0ex}{}{n}{i})(\genfrac{}{}{0ex}{}{n}{i-1})k^{i-1}.$

Si l'on pose $k=1$ dans cette formule, on obtient les nombres de Catalan, et pour $k=2$, les nombres de Schröder-Hipparque.

Relations de récurrence

Les nombres de Schröder-Hipparque peuvent être définis par relation de récurrence double ; partant de $s_0=s_1=1$ on a, pour $n⩾2$ :

$s_n=\frac{1}{n+1}((6n-3)s_{n-1}-(n-2)s_{n-2}).$

On peut déduire cette relation de la série génératrice ci-dessousModèle:,, mais Foata et Zeilberger en donnent une preuve combinatoire directe.

Ils peuvent aussi être définis par relation de récurrence forte ; partant de $s_0=1$, on a, pour $n⩾1$ :

$s_n=-s_{n-1}+2\sum _{k=0}^{n-1}{s}_k{s}_{n-1-k}$.

Série génératrice

Soit

$s(x)=s_0+s_{1}x+\cdots +s_n{x}^n+\cdots =1+x+3x^2+11x^3+45x^4+\cdots$

la série génératrice des nombres de Schröder-Hipparque. Elle satisfait à l'équation suivante :

$2x(s(x){)}^2-(1+x)s(x)+1=0$.

On obtient l'expression  :

$s(x)=\frac{1}{4x}(1+x-\sqrt{1-6x+x^2})$

Historique

D'après une ligne dans les Propos de table de Plutarque, Hipparque savait que le nombre de « propositions composées positives » que l'on peut former à partir de dix propositions simples est Modèle:Unité, et que le nombre de propositions négatives est Modèle:Unité. Cette affirmation est restée inexpliquée jusqu'en 1994, quand David Hough, un étudiant diplômé de l'université George-Washington, a observé qu'il y a Modèle:Unité façons de parenthéser une suite de dix élémentsModèle:,Modèle:,. Une explication semblable peut être donnée pour le deuxième nombre : il est très proche de (103049 + 518859)/2 = 310954 qui est la moyenne des dixième et onzième nombres de Schröder-Hipparque, et qui compte le nombre de parenthésages de dix termes avec un signe.

En mathématiques modernes, le problème de dénombrer les divers parenthésages a été introduit par Modèle:Harvsp.

Notes et références

Références

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Ouvrage.

Voir aussi

Articles connexes

• Subdivision d'un polygone

Liens externes

• Modèle:MathWorld
• « The Hipparchus Operad », The n-Category Café, Modèle:Date-.