I numeri di catalan
Re: I numeri di catalan
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
-
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
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,
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.
. 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.pdf ha scritto:The region bounded by the two paths is called a parallelogram polyomino.
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.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)
Re: I numeri di catalan
ok ho capito ora provo a ragionarci su .
Re: I numeri di catalan
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}
-
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
$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!
$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!
Ultima modifica di Gerald Lambeau il 27/09/2016, 18:48, modificato 1 volta in totale.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)
Re: I numeri di catalan
Ho capito il ragionamento l'unica cosa che non mi torna è perchè abbiamo detto che C_2=1? forse volevi dire A_2?
-
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
Sì, è vero, correggo subito.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)
Re: I numeri di catalan
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à?
A_{n-i+1}=C_{n-2-j-1}? perchè altrimenti come si prova l'identità?
-
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
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".
$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".
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)
Re: I numeri di catalan
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?