Accueil Préliminaires Définitions Dénombrement des faces Récurrence Classification Formule Dessin Dualité Dénombrement des tectoèdres
9 - Dénombrement des tectoèdres
Si la découverte des tectoèdres est récente, celle de la triangulation des polygones l'est beaucoup moins puisque Euler ( 1707 - 1783) lui-même s'y était intéressé. On sait calculer le nombre des triangulations possibles d'un polygone donné,. en fonction du nombre de ses côtés. Que peut-on en déduire pour le dénombrement des tectoèdres ?.
En fait , il y a deux problèmes différents à considérer.
1 Nombre de tectoèdres que l'on peut construire sur un polygone donné de n côtés:
Pour définir une triangulation d'un polygone, se donner sa formule ne suffit pas: Celle-ci définissant un cycle non orienté,, elle donne la répartition des faces et leur nature pour le polygone orienté arbitrairement et sur lequel on a choisi une origine arbitraire Pour obtenir toutes mes triangulations correspondant à une formule donnée on écrira donc celle-ci, ainsi que son inverse, en lui donnant comme terme initial successivement tous les termes de la formule.. En général, une formule d'ordre n peut donc définir 2n triangulations, mais si elle possède une particularité (symétrie, périodicité) la même triangulation pourra être obtenue plusieurs fois et le nombre des triangulations différentes sera inférieur à 2n.
Exemple
: Pour n=4, il y a 2 triangulations possibles de formules 1010 et 0101.Pour n = 5 la formule 20110 du pentagone étant symétrique ( on peut l'écrire 10201 ), on obtient 5 triangulations seulement chaque côté étant pris successivement pour côté initial: (20110, 01102, 11020, 10201, 02011 )
Par contre pour n=6, ( il y a 3 formules distinctes dans ce cas ) on obtient 14 triangulations : six à partir de la formule symétrique 301110, six également à partir de la formule périodique 210210 et deux à partir de la formule périodique 202020 ( le lecteur écrira lui-même les formules correspondantes).
Le nombre total des triangulations d'un polygone de n côtés, s'exprime à l'aide des nombres de Catalan.
Soit C(n) le n-ième nombre de Catalan Sa valeur est
C(n)= (2n)! / n! (n+1)!.
Si T(n) est le nombre des triangulations possibles d'un polygone de)n côtés, on démontre que T(n) = C( n-2) c'est-à-dire,
T(n) = ( 2n - 4)! / ( n-2)! (n-1)!
Voici les premières valeurs de ce nombre:
n: 3 4 5 6 7 8 9 10 11 12
¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾
T(n) : 1 2 5 14 42 132 429 1430 4862 16796
Que peut-on en déduire pour les tectoèdres ? Les éléments qui déterminent une triangulation bien déterminée,( formule, premier terme, sens de parcours) définissent en revanche toute une "famille" de tectoèdres. Nous avons vu, en effet, aussi bien dans le dessin d'un tectoèdre que dans la dualité qu'il y a une infinité de tectoèdres qui correspondent à ces données Le nombre T(n) ci-dessus est donc le nombre de ces familles de tectoèdres que l'on peut construire sur un polygone donné. Par exemple à un quadrilatère, on peut associer deux triangulations (fig 1 ) auxquelles correspondent deux familles de tectoèdres (fig2).
2. Nombre de formules des tectoèdres ( donc des triangulations ) que l'on peut obtenir avec un polygone de n côtés
Les tectoèdres nous intéressent maintenant seulement par leur formule (alors que dans le cas précédent, on tenait compte aussi de leur position) Le nombre que nous cherchons est donc celui de leurs formules, étant entendu que deux formules ne différant que par leur sens et par leur premier terme ne sont pas considérées comme distinctes.
Ce nombre se déduit du résultat précédent., en tenant compte, cette fois-ci, des particularités géométriques( symétries, périodes ) que présente la formule.
Soit F(n) le nombre de ces tectoèdres pour l'ordre n Ce nombre est donné par: la formule suivante:
dans laquelle, on convient de considérer comme nulle toute factorielle portant sur un nombre non entier .
Sinon il faut donner quatre formules différentes, suivant que n est de la forme 6k, 6k ± 1, 6k ± 2 ou 6k + 3, avec k entier. Si on désigne par A,B,C,D les quatre termes de la somme ci-dessus, on a alors
Si n = 6k F(n) = A + B + D
n = 6k ± 1 F(n) = A + C
n = 6k ± 2 F(n) = A + B
n = 6k + 3 F(n) = A + C + D
Voici les premières valeurs de F(n):
n : 3 4 5 6 7 8 9 10 11 12 13 14 15
¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾
F(n) : 1 1 1 3 4 12 27 82 228 733 2282 7528 24834
Le nombre F(n) est évidemment inférieur au nombre T(n)
Il augmente très vite avec n: pour n = 20 il dépasse déjà 10 millions