2.6 Problème de triangulation

De combien de façons différentes un polygone à $\displaystyle n$ côtés peut-il être divisé en triangles ? La solution de ce problème a été trouvée par Léonard Euler. Cette suite de nombres apparait dans plusieurs problèmes de combinatoire. Ils sont nommés en l’honneur du mathématicien belge Eugène Charles Catalan (1814-1894), qui les a étudiés. Il s’agit de l’une des suites de nombres parmi les plus importantes de la combinatoire. Nous allons donc définir $\displaystyle C_{n}$ comme étant le nombre de façons de trianguler un polygone à $\displaystyle n+2$ côtés et chercher une relation de récurrence nous permettant de les calculer.

Pour ce faire, commençons par regarder quelques cas particulier. Il est facile de voir qu’il n’y a qu’une seule façon de trianguler un triangle, on a donc $\displaystyle C_{1}=1$ . Dans le cas d’un quadrilatère, il y a deux possibilités comme illustré ci-contre. On écrira donc $\displaystyle C_{2}=2$ .	Triangulation d’un quarilatère
Pour le pentagone, un peu plus de travail est nécessaire, mais comme l’illustre la figure ci-contre, il n’est pas très difficile d’obtenir qu’il y a un total de $\displaystyle 5$ possibilités. On dira donc que $\displaystyle C_{3}=5$	Triangulation du pentagone

À partir de l’hexagone, les choses commencent à se compliquer un peu, et le nombre de cas augmente rapidement. Nous allons donc chercher à établir une relation de récurrence. L’idée est d’utiliser à nouveau la méthode de l’élément distingué. Prenons un polygone à $\displaystyle n+2$ côtés, et choisissons un côté quelconque. Ce côté doit obligatoirement faire partie d’un des triangles de notre triangulation. Si le polygone possède $\displaystyle n+2$ côtés, nous aurons donc $\displaystyle n$ choix de triangles qui peuvent contenir le côté choisi.

Chacun de ces triangles divise le polygone original en trois régions. Au centre, un triangle; à gauche et à droite, deux nouveaux polygones que nous devons trianguler. Par exemple, le triangle en rouge ci dessus nous donne un triangle à sa gauche et un pentagone à sa droite. Donc une fois que le triangle rouge est fixé, d’après le principe du produit, il y a $\displaystyle C_{1}C_{3}$ façons de trianguler la figure en incluant ce triangle (le rouge). Maintenant, il faut considérer tous les triangles pour lesquels un côté est le côté choisi. Le principe de la somme nous affirme donc, dans le cas précis de l’heptagone ci-dessus, que:

\displaystyle C_{5}=C_{0}C_{4}+C_{1}C_{3}+C_{2}C_{2}+C_{3}C_{1}+C_{4}C_{0}

Cette récurrence peut bien entendu être généralisé à tout les polygônes à $\displaystyle n+2$ côtés, on obtient donc:

\displaystyle C_{n}=\sum_{k=0}^{n-1}C_{k}C_{n-k-1}

Il reste cependant un problème important. Quelle est la valeur de $\displaystyle C_{0}$ ? C’est à dire, combien y a-t-il de façons de trianguler un polygone à $\displaystyle 2$ côtés ? Le problème n’ayant pas de sens précis géométriquement, nous allons utiliser les valeurs que nous avons déjà trouvé pour la calculer. En utilisant la valeur de $\displaystyle C_{3}$ , on obtient donc:

$\displaystyle\displaystyle C_{3}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle C_{0}C_{2}+C_{1}C_{1}+C_{2}C_{0}$
$\displaystyle\displaystyle 5$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 2C_{0}+1+2C_{0}$
$\displaystyle\displaystyle 4C_{0}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 4$
$\displaystyle\displaystyle C_{0}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 1$

Nous sommes maintenant en mesure de calculer la valeur de $\displaystyle C_{n}$ pour différentes valeurs de $\displaystyle n$ , ce qui peut être accompli à l’aide de Python.

Listing 11: Problème de triangulation

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def Catalan(n):


              6
              
              
              
                if n == 0:


              7
              
              
              
                    return 1


              8
              
              
              
                else:


              9
              
              
              
                    return sum([Catalan(i) * Catalan(n-i-1) for i in range(0,n)])


              10
              
              
              
            


              11
              
              
              
            tableau = DataFrame([[Catalan(n) for n in range(0,9)]])


              12
              
              
              
            tableau.index = ["Catalan"]


              13
              
              
              
            tableau

On obtient donc:

$\displaystyle n$	0	1	2	3	4	5	6	7	8
$\displaystyle C_{n}$	1	1	2	5	14	42	132	429	1430

Notez que les nombres de Catalan possèdent une formule explicite relativement simple. Cette dernière est cependant hors de notre portée pour le moment. Nous aurons cependant l’occasion d’y revenir plus tard.