Nombre de Schröder-Hipparque

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 n de 0 à 9) sont :

{\begin{matrix}n&0&1&2&3&4&5&6&7&8&9\\s_{n}&1&1&3&11&45&197&903&4279&20793&103049\end{matrix}}

voir la suite A001003 de l'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

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

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 Stanley 1999, vol. 2, Exercice 6.39.

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 permutoèdres (en) : 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'entiers^,. La k-ième suite de cette famille de suites d'entiers est la suite

x_{1},x_{2},\ldots ,x_{n},\ldots

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}}{n \choose i}{n \choose 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\geqslant 2$ :

s_{n}={\frac {1}{n 1}}{\Big (}(6n-3)s_{n-1}-(n-2)s_{n-2}{\Big )}.

On peut déduire cette relation de la série génératrice ci-dessous^,, 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\geqslant 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}}{\Big (}1 x-{\sqrt {1-6x x^{2}}}{\Big )}

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 103 049, et que le nombre de propositions négatives est 310 952. 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 103 049 façons de parenthéser une suite de dix éléments^,^,. 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 Schröder 1870.

Notes et références

Notes

Références

(en) F. Acerbi, « On the shoulders of Hipparchus: A reappraisal of ancient Greek combinatorics », Arch. Hist. Exact Sci., vol. 57,‎ 2003, p. 465-502 (lire en ligne [archive du 21 juillet 2011]).
(en) M. Bernstein et Neil Sloane, « Some canonical sequences of integers », Linear Algebra Appl., vol. 226/228,‎ 1995, p. 57-72 (DOI 10.1016/0024-3795(94)00245-9, MR 1344554).
(en) William Y. C. Chen, Toufik Mansour et Sherry H. F. Yan, « Matchings avoiding partial patterns », Electronic Journal of Combinatorics, vol. 13, n^o 1,‎ 2006, article n^o 112(electronic) (MR 2274327, lire en ligne).
(en) Curtis Coker, « A family of eigensequences », Discrete Math., vol. 282, n^os 1-3,‎ 2004, p. 249-250 (DOI 10.1016/j.disc.2003.12.008, MR 2059525).
(en) Ivor M. H. Etherington, « Some problems of non-associative combinations (I) », Edinburgh Mathematical Notes, vol. 32,‎ 1940, p. 1-6 (DOI 10.1017/S0950184300002639).
(en) Dominique Foata et Doron Zeilberger, « A classic proof of a recurrence for a very classical sequence », J. Combin. Theory Ser. A, vol. 80, n^o 2,‎ 1997, p. 380-384 (DOI 10.1006/jcta.1997.2814, MR 1485153, arXiv math/9805015).
(en) Ralf Holtkamp, « On Hopf algebra structures over free operads », Adv. Math., vol. 207, n^o 2,‎ 2006, p. 544-565 (DOI 10.1016/j.aim.2005.12.004, MR 2271016, arXiv math/0407074).
(en) Ernst Schröder, « Vier combinatorische Probleme », Z. Angew. Math. Phys., vol. 15,‎ 1870, p. 361-376.
(en) Louis W. Shapiro et Robert A. Sulanke, « Bijections for the Schröder numbers », Mathematics Magazine, vol. 73, n^o 5,‎ 2000, p. 369-376 (DOI 10.2307/2690814, MR 1805263).
(en) Richard P. Stanley, « Hipparchus, Plutarch, Schröder, and Hough », Amer. Math. Monthly, vol. 104, n^o 4,‎ 1997a, p. 344-350 (DOI 10.2307/2974582, MR 1450667, lire en ligne).
(en) Richard P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge/New York/Melbourne etc., Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics » (n^o 49), 1997b, 2^e éd. (ISBN 978-0-521-55309-4 et 0-521-55309-1, présentation en ligne).
(en) Richard P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge/New York/Melbourne etc., Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics » (n^o 62), 1999, 585 p. (ISBN 0-521-56069-1, présentation en ligne).