I numeri di catalan

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

Re: I numeri di catalan

Messaggioda Ila_mengu » 13/09/2016, 15:40

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
Ila_mengu
 
Messaggi: 19
Iscritto il: 12/09/2016, 13:15

Re: I numeri di catalan

Messaggioda Gerald Lambeau » 13/09/2016, 16:00

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,
pdf ha scritto: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.
"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)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: I numeri di catalan

Messaggioda Ila_mengu » 13/09/2016, 16:15

ok ho capito ora provo a ragionarci su . :D
Ila_mengu
 
Messaggi: 19
Iscritto il: 12/09/2016, 13:15

Re: I numeri di catalan

Messaggioda Ila_mengu » 27/09/2016, 14:28

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}
Ila_mengu
 
Messaggi: 19
Iscritto il: 12/09/2016, 13:15

Re: I numeri di catalan

Messaggioda Gerald Lambeau » 27/09/2016, 16:12

$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!
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)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: I numeri di catalan

Messaggioda Ila_mengu » 27/09/2016, 18:42

Ho capito il ragionamento l'unica cosa che non mi torna è perchè abbiamo detto che C_2=1? forse volevi dire A_2?
Ila_mengu
 
Messaggi: 19
Iscritto il: 12/09/2016, 13:15

Re: I numeri di catalan

Messaggioda Gerald Lambeau » 27/09/2016, 18:47

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)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: I numeri di catalan

Messaggioda Ila_mengu » 27/09/2016, 18:53

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à?
Ila_mengu
 
Messaggi: 19
Iscritto il: 12/09/2016, 13:15

Re: I numeri di catalan

Messaggioda Gerald Lambeau » 27/09/2016, 19:39

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".
"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)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: I numeri di catalan

Messaggioda Ila_mengu » 27/09/2016, 20:11

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?
Ila_mengu
 
Messaggi: 19
Iscritto il: 12/09/2016, 13:15

PrecedenteProssimo

Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti