Buongiorno a tutti .. Qualcuno saprebbe dimostrarmi che presi 2n punti su una circonferenza il numero di modi di unire a due a due i punti con n corde senza che si intersechino è un numero di catalan?
Un ultima cosa : mi servirebbe provare che il numero di poliomini parallelogrammi con un semiperimetro di n+1 è un numero di catalan
I numeri di catalan
-
Gerald Lambeau
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
Sarò poco formale, ma abbastanza puntiglioso.
Chiamiamo $A_1, A_2, \dots, A_{2n}$ i punti sulla circonferenza e chiamiamo, con molta fantasia, $C_n$ il numero di modi di fare quello che vogliamo fare.
Notiamo una bella cosa: se $A_1$ lo collego a un punto con indice dispari, in mezzo a loro ci sta un numero dispari di punti che non si possono collegare ad altri altrimenti tagliano la corda passante per $A_1$, quindi si collegano fra loro, ma allora ne avanza uno, e a me non va bene 'sta cosa!
Allora colleghiamo $A_1$ a $A_{2(i+1)}$, e questo lo posso fare per $i=0, 1, \dots, n-1$. Ora non ci resta che dimostrare che il numero di modi di fare quella cosa quando $A_1$ è collegato a $A_{2(i+1)}$ è $C_i \cdot C_{n-i-1}$ e il gioco è fatto.
La corda $A_1A_{2(i+1)}$ mi divide l'insieme di punti in due gruppi da $2i$ e da $2(n-i-1)$ punti, i primi li posso collegare in $C_i$ modi e i secondi in $C_{n-i-1}$ moltiplico per trovare il numero di modi totale e mi torna! Sono felice? NO!
Mancano due dettagli:
- siamo sicuri che un punto di un gruppo non si collega a un punto di un altro gruppo? Beh, in caso taglierebbero la corda $A_1A_{2(i+1)}$, quindi questo non si può;
- siamo sicuri che, prendiamo per esempio il gruppo di $2i$ punti, $C_i$ sia esattamente il numero di modi di collegarli in questa situazione? Ignoriamo gli altri punti, sappiamo che possiamo farlo in $C_i$ modi, quindi sappiamo che il numero di modi è al più $C_i$. Ora consideriamo di nuovo gli altri punti. È palese che le corde che si sono andate a formare nel gruppo di $2i$ punti, mentre ignoravamo gli altri, non superano la corda $A_2A_{2(i+1)-1}$, e quindi non tagliano né la corda $A_1A_{2(i+1)}$ né tutte quelle che si formano con gli altri vertici, dunque ogni modo dei $C_i$ considerati va bene, quindi il numero di modi è almeno $C_i$, quindi sì, $C_i$ è il numero giusto. Il caso in cui consideriamo il gruppo di $2(n-i-1)$ punti è analogo (per essere pignoli al massimo andrebbero fatti praticamente in contemporanea nella propria testa, ma lasciamo stare, dovresti esserti già convinto così).
Quindi ora siamo contenti, giusto? SBAGLIATO! E se $i=0$? Oppure se $i=n-1$? Dobbiamo porci la domanda: quant'è $C_0$? Beh con $0$ punti c'è un solo modo, non mettere corde, e pure nei casi più grandi che vado a considerare l'unico modo di unire gruppi da $0$ punti è senza mettere corde, quindi possiamo dire che $C_0=1$ senza problemi.
Ora siamo felici? Sì, perché abbiamo trovato che $\displaystyle C_n=\sum_{i=0}^{n-1} C_i \cdot C_{n-i-1}$, quindi $C_n$ è l'$n$-esimo numero di Catalan!
Chiamiamo $A_1, A_2, \dots, A_{2n}$ i punti sulla circonferenza e chiamiamo, con molta fantasia, $C_n$ il numero di modi di fare quello che vogliamo fare.
Notiamo una bella cosa: se $A_1$ lo collego a un punto con indice dispari, in mezzo a loro ci sta un numero dispari di punti che non si possono collegare ad altri altrimenti tagliano la corda passante per $A_1$, quindi si collegano fra loro, ma allora ne avanza uno, e a me non va bene 'sta cosa!
Allora colleghiamo $A_1$ a $A_{2(i+1)}$, e questo lo posso fare per $i=0, 1, \dots, n-1$. Ora non ci resta che dimostrare che il numero di modi di fare quella cosa quando $A_1$ è collegato a $A_{2(i+1)}$ è $C_i \cdot C_{n-i-1}$ e il gioco è fatto.
La corda $A_1A_{2(i+1)}$ mi divide l'insieme di punti in due gruppi da $2i$ e da $2(n-i-1)$ punti, i primi li posso collegare in $C_i$ modi e i secondi in $C_{n-i-1}$ moltiplico per trovare il numero di modi totale e mi torna! Sono felice? NO!
Mancano due dettagli:
- siamo sicuri che un punto di un gruppo non si collega a un punto di un altro gruppo? Beh, in caso taglierebbero la corda $A_1A_{2(i+1)}$, quindi questo non si può;
- siamo sicuri che, prendiamo per esempio il gruppo di $2i$ punti, $C_i$ sia esattamente il numero di modi di collegarli in questa situazione? Ignoriamo gli altri punti, sappiamo che possiamo farlo in $C_i$ modi, quindi sappiamo che il numero di modi è al più $C_i$. Ora consideriamo di nuovo gli altri punti. È palese che le corde che si sono andate a formare nel gruppo di $2i$ punti, mentre ignoravamo gli altri, non superano la corda $A_2A_{2(i+1)-1}$, e quindi non tagliano né la corda $A_1A_{2(i+1)}$ né tutte quelle che si formano con gli altri vertici, dunque ogni modo dei $C_i$ considerati va bene, quindi il numero di modi è almeno $C_i$, quindi sì, $C_i$ è il numero giusto. Il caso in cui consideriamo il gruppo di $2(n-i-1)$ punti è analogo (per essere pignoli al massimo andrebbero fatti praticamente in contemporanea nella propria testa, ma lasciamo stare, dovresti esserti già convinto così).
Quindi ora siamo contenti, giusto? SBAGLIATO! E se $i=0$? Oppure se $i=n-1$? Dobbiamo porci la domanda: quant'è $C_0$? Beh con $0$ punti c'è un solo modo, non mettere corde, e pure nei casi più grandi che vado a considerare l'unico modo di unire gruppi da $0$ punti è senza mettere corde, quindi possiamo dire che $C_0=1$ senza problemi.
Ora siamo felici? Sì, perché abbiamo trovato che $\displaystyle C_n=\sum_{i=0}^{n-1} C_i \cdot C_{n-i-1}$, quindi $C_n$ è l'$n$-esimo numero di Catalan!
Ultima modifica di Gerald Lambeau il 12/09/2016, 15:35, 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
Non mi è chiaro il fatto che la corda A_1 A_{2(i+1)} divide l'insieme di punti in quei due gruppi di punti. Per esempio se prendo n=4 avrò sulla circonferenza 8 punti e se prendo quindi i=2 dovrò collegare il punto A_1 con il punto A_{2(2+1)}=A_6 ma in questo modo vedo a sinistra della corda 2 punti ma alla destra 4 punti che non sono gli n-i-1 ovvero 4-2-1=1
-
Gerald Lambeau
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
Sì, hai ragione, correggo alcune cose.
"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)
-
Gerald Lambeau
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
Adesso dovrebbe tornarti.
"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, adesso è più chiaro grazie mille.
Invece il discorso riguardante i poliomini parallelogrammi sai qualcosa?
Invece il discorso riguardante i poliomini parallelogrammi sai qualcosa?
-
Gerald Lambeau
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
Non so cosa siano e cercando su google non ho trovato molto, ma se il nome non mi inganna sono come i tetramini estesi a più quadrati, giusto?
"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
si esatto sono praticamente un insieme connesso di celle di lunghezza unitaria.
E la prima volta che uso questo forum quindi non so bene come si faccia a mandare un immagine.
E la prima volta che uso questo forum quindi non so bene come si faccia a mandare un immagine.
-
Gerald Lambeau
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: I numeri di catalan
Tranquillo, l'immagine ce l'ho in testa. Possono contenere dei "buchi"? Cioè, roba tipo un quadrato $3 \times 3$ senza il quadratino centrale?
"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
No non possono contenere buchi. Partendo da un quadratino per aggiungerne un altro lo si può fare solo aggiungendolo o sulla sua destra o in altro . I poliomini parallelogrammi sono tali che il semiperimetro è la somma della sua altezza (insieme delle righe di quadrati) con la sua larghezza (insieme delle colonne di quadrati)