Nombre de Schröder-Hipparque

En théorie des nombres, les nombres de Schröder-Hipparque forment une suite d'entiers qui servent à compter les arbres planaires avec un ensemble donné de feuilles, les insertions de parenthèses dans une suite, et le nombre de façons de découper un polygone convexe en polygones plus petits par l'insertion de diagonales. Cette suite de nombres commence par

Les onze subdivisions d'un pentagone.
1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859,... (c'est la suite A001003 de l'OEIS).

Ils sont aussi appelés nombres super-Catalans, petits nombres de Schröder, ou nombres d'Hipparque, d'après Eugène Charles Catalan et ses nombres de Catalan, Ernst Schröder et ses (grands) nombres de Schröder très voisins, et d'après le mathématicien et astronome grec Hipparque qui, selon Plutarque, connaissait certainement ces nombres.

Applications en combinatoire énumérative

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

Les nombres de Schröder-Hipparque peuvent servir à dénombrer des objets combinatoires dont on sait par ailleurs qu'ils sont étroitement reliés[1] ,[2],[3],[4] :

  • Le n-ième nombre de la suite 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 planaires à n feuilles, et dont les nœuds internes ont deux enfants ou plus.
  • 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 Kn + 1, de dimension n − 1, y compris l'associaèdre lui-même vue comme une face, mais sans compter l'ensemble vide. Par exemple, l'associaèdre K4, 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 énumérés par une même suite d'entiers[2].

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

D'autres interprétations sont données dans Stanley 1999, vol. 2, Exercice 6.39.

Suites voisines

modifier
  • Les nombres de Schröder ou grands nombres de Schröder sont juste le double des nombres de Schröder-Hipparque, et comptent divers types d'objets combinatoire 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 la suite entière.
  • Les nombres de Catalan aussi comptent 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[3].
  • On peut faire un parallèle entre les associaèdres et les permutoèdres (en) : les nombres de Schröder-Hipparque comptent les faces et les nombres de Catalan les sommets d'un associaèdre; les nombres correspondants pour le permutoèdre sont les nombres de Bell ordonnés et les factorielles.

Expressions

modifier

La suite des nombres de Catalan et la suite des nombres de Schröder-Hipparque peuvent être vues comme des vecteurs. Ils 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[6],[7]. La k-ième suite dans cette famille de suites d'entiers est la suite

 

où les   sont obtenus comme la somme des nombres de Narayana multipliés par les puissances de k :

 

Si l'on pose   dans cette formule, on obtient les nombres de Catalan, et pour  , la formule donne les nombres de Schröder-Hipparque[7].

Relation de récurrence

modifier

De manière équivalant à la formule sommatoire ci-dessus, les nombres de Schröder-Hipparque peuvent aussi bien être définis par une relation de récurrence :

 

Stanley en donne une preuve par les séries génératrices[8]. Cette série est

 

Foata et Zeilberger en donnent une preuve combinatoire directe[9].

Historique

modifier

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[1],[8],[10]. 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[10].

En mathématiques modernes, le problème de compter les divers parenthésages a été introduit par Schröder 1870.

Notes et références

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Schröder–Hipparchus number » (voir la liste des auteurs).
  1. a et b Stanley 1997b, vol. I, Exercise 1.45, p. 51 et Stanley 1999, vol. II, p. 176-178 et 213.
  2. a et b Shapiro et Sulanke 2000.
  3. a et b Etherington 1940.
  4. Holtkamp 2006.
  5. Chen, Mansour et Yan 2006.
  6. Bernstein et Sloane 1995.
  7. a et b Coker 2004.
  8. a et b Stanley 1997a.
  9. Foata et Zeilberger 1997.
  10. a et b Acerbi 2003.

Références

modifier

Voir aussi

modifier

Articles connexes

modifier

Liens externes

modifier