I numeri di catalan

[Ila_mengu]

Ho dato una letta ora non dovrebbe essere così difficile la spiegazione xo forse sarebbe utile un disegnino .. Xk non ho ben capito cosa intendi per percorso superiore e inferiore del poliomino

[Gerald Lambeau]

Qui http://www-math.mit.edu/~rstan/ec/catsol.pdf, proprio nella sezione che mi hai detto tu, dice, e cito così non ti confondo troppo,

The region bounded by the two paths is called a parallelogram polyomino.

. Guarda il disegno, e osserva che dal vertice più in basso a sinistra al vertice più in altro a destra del poliomino vanno due percorsi, uno che delimita i bordi superiori e di sinistra, l'altro che delimita i bordi inferiori e di destra.
La spiegazione che ti ho fatto con questi percorsi, riconducendoli a parentesi aperte e chiuse, era per farti capire cosa contano i +1 e -1 del pdf e come lo contano, e anche per farti notare la bigezione con il problema originale.

[Ila_mengu]

ok ho capito ora provo a ragionarci su .

[Ila_mengu]

Avrei un ultima domanda: vorrei dimostrare che il numero di triangolazioni di un poligono regolare convesso con n lati il cui insieme di modi chiameremo con A_n è esattamente il numero di Catalan C_{n-2}

[Gerald Lambeau]

$A_2=1=C_0$, l'unico modo per triangolare un segmento è non triangolarlo.
$A_3=1=C_1$, cioè non tracciare alcun segmento è l'unico modo di triangolare un triangolo (ma questo non serviva dirlo in realtà, il conto torna).
Indovina un po' cosa vogliamo? Vorremmo che $\displaystyle A_n=\sum_{i=2}^{n-1} A_i \cdot A_{n-i+1}=\sum_{j=0}^{n-3} C_j \cdot C_{n-2-j-1}=C_{n-2}$, dove vale, per gli indici, che $j=i-2$.
Numeriamo i vertici con $1, 2, \dots, n$. Il segmento $1-n$ dovrà appartenere a un triangolo. Che succede se scelgo come terzo vertice, con molta fantasia, il vertice $i$? Che da $1$ a $i$ ci sono $i$ vertici che formano un poligono da triangolare in $A_i$, da $i$ a $n$ ce ne sono $n-i+1$ da triangolare in $A_{n-i+1}$ modi, per un totale di $A_i \cdot A_{n-i+1}$ modi. E se $i=2$? Torna, perché abbiamo detto che $A_2=1$. E se $i=n-1$? Torna lo stesso, sempre perché $A_2=1$.
Ma allora, $A_n$ è la somma dei modi possibili per ogni $i$ scelto, e $i$ va proprio da $2$ a $n-1$, quindi è la somma voluta!

[Ila_mengu]

Ho capito il ragionamento l'unica cosa che non mi torna è perchè abbiamo detto che C_2=1? forse volevi dire A_2?

[Gerald Lambeau]

Sì, è vero, correggo subito.

[Ila_mengu]

scusami se ti rompo ancora. Ma non ho ben capito perchè alla fine le due somme coincidono. forse salto qualche passaggio ma abbiamo dimostrato che A_i=C_j e
A_{n-i+1}=C_{n-2-j-1}? perchè altrimenti come si prova l'identità?

[Gerald Lambeau]

Allora: $A_i=C_{i-2}=C_j$ (diciamo per ipotesi induttiva, con un'induzione forte).
$A_{n-i+1}=C_{n-i+1-2}=C_{n-i-1}=C_{n-(j+2)-1}=C_{n-2-j-1}$, dove anche qui usiamo la nostra ipotesi induttiva. Qua si vede di più a cosa serve il passaggio dall'indice $i$ all'indice $j=i-2$: senza un secondo indice mi sarebbe stato difficile spiegare il perché di questa specie di "salto".

[Ila_mengu]

ok ho capito. Quindi invece di stare a scrivere i casi per i=2 e i=n-1 posso anche scrivere: dato che i valori iniziali sono uguali le due successioni coincidono. Giusto?