Problema
Sia dato un poligono convesso di \(n\) lati. Calcolare in quanti modi diversi il poligono può essere diviso in triangoli mediante diagonali che non si intersecano.
Questo problema venne proposto da Eulero nel 1751 al suo amico Christian Goldbach. Il numero delle diverse triangolazioni trovato da Eulero, indicato con \(E_{n}\), è il seguente:
\[ E_{n} = \frac {2 \cdot 6 \cdot 10 \cdots (4n-10)}{(n-1)!} \]Se \(n=3\) abbiamo \(E_{3}=1\).
Se \(n=4\) abbiamo \(E_{4}=2\).
Nel caso di un pentagono abbiamo \(E_{5}=5\), come si vede dal seguente prospetto:
1) Soluzione con il metodo della funzione generatrice
Sia dato un poligono di \(n\) lati con i vertici numerati da \(v_{1},v_{2}, \cdots v_{n}\). Indichiamo con \(E_{n}\) il numero delle diverse decomposizioni in triangoli per un poligono di \(n\) lati. Prendiamo un lato qualsiasi, ad esempio il lato con i vertici \(v_{1},v_{2}\). È evidente che questo lato sarà la base di un triangolo in ognuna delle \(E_{n}\) decomposizioni. Al triangolo di vertici \(v_{1},v_{2},v_{3}\) corrispondono \(E_{n-1}\) decomposizioni. Al triangolo di vertici \(v_{1},v_{2},v_{4}\) corrispondono \(E_{3}E_{n-2}\) decomposizioni, e così via. Queste decomposizioni sono tutte distinte e quindi il numero totale delle triangolazioni è dato dalla seguente formula:
\[ E_{n}= E_{2}E_{n-1} + E_{3}E_{n-2} + \cdots + E_{n-1}E_{2} \]dove abbiamo posto per uniformità \(E_{2}=1\). Questa formula di ricorrenza è stata introdotta da Segner nel 1758.
Calcoliamo ora la funzione generatrice dei numeri \(E_{n}\):
dove \(E_{0}=E_{1}=0\).
Se calcoliamo il quadrato della \(F(x)\), con la regola del prodotto fra due polinomi, abbiamo:
\[ (F(x))^{2} = E_{3} \cdot x^{4} + E_{4} \cdot x^{5} + E_{5} \cdot x^{6} + \cdots \]in virtù dell’equazione di ricorrenza soddisfatta dai coefficienti \(E_{n}\). Con semplici passaggi possiamo scrivere l’equazione funzionale soddisfatta dalla funzione \(F(x)\):
\[ F(x)^2 – xF(x) + x^{3} = 0 \]Le condizioni iniziali sono \(F(0)=0\) e \(F'(0)=0\), dove il simbolo \(F'(0)\) indica la derivata calcolata nel punto \(x=0\). Risolvendo rispetto a \(F(x)\) e tenendo conto delle condizioni iniziali troviamo la seguente soluzione (l’altra col segno positivo si scarta):
\[ F(x)= x \left(\frac{1- \sqrt{1- 4x}}{2}\right) \]Utilizziamo ora lo sviluppo in serie di Taylor-McLaurin della funzione \(\sqrt{1-4x}\), cioè la formula binomiale di Newton, valida per \(|x| < 1\) e per ogni numero reale \(\alpha\):
\[ (1+t)^{\alpha} = \sum_{k=0}^{\infty}{\binom{\alpha}{k} t^{k}} = 1 + \alpha t + \frac{\alpha \cdot (\alpha -1)t^{2}}{2!} + \frac{\alpha \cdot (\alpha -1)(\alpha -2)t^{3}}{3!} + \cdots \]Nel nostro caso \(\alpha = \frac{1}{2}\) e \(t=-4x\). Il coefficiente binomiale \(\binom {\frac {1}{2}}{n}\) ha la seguente espressione:
\[ \binom{\frac{1}{2}}{n} = \frac{(\frac{1}{2})(\frac{-1}{2})(\frac{-3}{2}) \cdots (\frac{-(2n-3)}{2})}{n!} = \frac{(-1)^{n-1}}{2^{2n-1}n} \binom{2n-2}{n-1} \]dove abbiamo utilizzato la seguente formula, che si dimostra facilmente con il metodo di induzione:
\[ 1 \cdot 3 \cdot 5 \cdots \cdot (2n-1)= \frac {(2n)!}{2^{n}n!} \]Proseguendo abbiamo:
\[ \binom {\frac {1}{2}}{n}(-4)^{n}=\left(\frac{-2}{n}\right)\binom {2n-2}{n-1} \]Mettendo insieme quanto trovato abbiamo infine che il coefficiente davanti alla potenza \(x^{n}\) della funzione generatrice \(F(x)\) è:
\[ E(n)=\frac {1}{n-1} \binom {2n-4}{n-2} \]L’espressione trovata coincide con il numero di Catalan \(C_{n-2}\), dove \(C_{n}= \frac{1}{n+1} \binom {2n}{n}\) e \(C_{0}=1\). Ricordiamo che talvolta viene scritto \(C_{n+1}\) al posto di \(C_{n}\); ciò dipende dalla scelta dei valori iniziali della successione \(\{C_{n}\}\).
Per uno studio esaustivo delle proprietà e delle applicazioni dei numeri di Catalan vedere il testo [1] (disponibile su Amazon.com).
Esercizio 1
Dimostrare la seguente formula di ricorrenza dei numeri di Catalan, per \(n > 0\):
Esercizio 2
Dimostrare la seguente formula di ricorrenza per \(E(n)\):
Esercizio 3
Dimostrare che anche la formula trovata da Eulero
verifica la stessa equazione di ricorrenza dell’esercizio 2.
2) La soluzione di Lamé
Il matematico francese Lamé (1795-1870) risolse il problema con una strategia diversa. Invece di utilizzare un lato del poligono per enumerare i triangoli utilizzò le diagonali. Ad ognuna delle \((n-3)\) diagonali corrisponde un gruppo di decomposizioni, dove la diagonale costituisce un lato di due triangoli adiacenti. Il problema che sorge è che non tutti i triangoli delle decomposizioni sono compresi se si parte da una singola diagonale. Se tuttavia facciamo questa operazione partendo da ogni vertice del poligono, allora sicuramente tutti i triangoli sono compresi, e otteniamo questo numero complessivo:
\[ n(E_{3}E_{n-1}+ E_{4}E_{n-2} + \cdots +E_{n-1}E_{3}) \]Tuttavia in questo modo i triangoli sono conteggiati più volte. Per calcolare il numero esatto \(E(n)\) dobbiamo quindi evitare di contare più volte la stessa decomposizione. Per questo immaginiamo un’arbitraria decomposizione di \(n-2\) triangoli, con \(3(n-2)\) lati. Togliamo da questa i lati del poligono e dividiamo per due ottenendo \(n-3\), che corrisponde al numero delle diagonali che appaiono nella data decomposizione. Questa particolare decomposizione è ripetuta per quanti sono gli estremi di queste diagonali, cioè \(2n-6\). È questo il fattore di ripetizione cercato; quindi il numero totale delle decomposizioni trovato da Lamé è il seguente:
\[ E(n) = \frac{n(E_{3}E_{n-1} + E_{4}E_{n-2} + \cdots + E_{n-1}E_{3})}{2n-6} \]Esercizio 4
Dimostrare nuovamente la formula di ricorrenza:
senza utilizzare l’espressione dei numeri di Catalan.
Dimostrazione
Scriviamo prima l’equazione di ricorrenza per un poligono di \(n+1\) lati:
Mettendo insieme questa formula con l’espressione trovata da Lamé dimostriamo facilmente la formula di ricorrenza.
Bibliografia
[1]R. Stanley – Catalan Numbers (Cambridge University Press)
0 commenti