Subdivision d'un polygone

Équivalence combinatoire entre subdivisions de polygones, arbres planaires et parenthésages

En mathématiques, une subdivision d'un polygone consiste à découper ce dernier par l'ajout de diagonales.

Les subdivisions de polygone peuvent servir à modéliser d'autres objets combinatoires. En effet les subdivisions d'un polygone à $n$ côtés en $k$ parts peuvent s'interpréter comme :

• Les arbres planaires à $n-1$ feuilles et $n+k-2$ branches, et dont les nœuds portent deux branches ou plus.
• le nombre de façons de parenthéser $n-1$ éléments avec $k-1$ paires de parenthèses, de sorte que toute paire de parenthèses entoure au moins deux symboles, et sans paire de parenthèses entourant tous les éléments.

Dénombrement

Le nombre de subdivisions d'un polygone à $n+2$ côtés est donné par le $n$-ème nombre de Schröder-Hipparque.

Le nombre de subdivisions d'un polygones à $n+2$ côtés en $k$ parts est donné par la formule $\frac{1}{n}(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n+k}{n+1})$.

Ces nombres s'interprètent également comme le nombre de $k$-faces de l'associaèdre $K_{n-1}$. On obtient alors le triangle ci-dessous (Modèle:OEIS) :

k = 1 2 3 4 5 n 1 1 1 2 1 2 3 3 1 5 5 11 4 1 9 21 14 45 5 1 14 56 84 42 197

Subdivisions de polygones non équivalentes par rotation et réflexion, avec 3,4,5,6,7 et 8 côtés.

Des subdivisions de polygones sont dites équivalentes si elles peuvent s'obtenir par réflexion ou rotation l'une de l'autre.

Ainsi pour $n=3,4,5,6,7,8...$ il existe $1,2,3,9,20,75...$ subdivisions non équivalentes (Modèle:OEIS).

Parmi elles certaines sont chirales ($2,15,47...$ subdivisions chirales pour $n=6,7,8...$ côtés). Le nombre de subdivisions non équivalentes par rotation seulement vaut donc $1,2,3,11,29,122...$ (Modèle:OEIS).