[N] Binomiali e fattoriali.
Moderatore: tutor
<!-- BBCode Start --><B><font color=blue>Problema 1</font></B><!-- BBCode End -->: dimostrare che, per ogni m, n \\in N<sub>0</sub> tali che n >= m,
<BR>[gcd(m, n)/n] · Bin(n, m) è un numero intero, ove Bin(n, m) denota - come al solito - il coefficiente binomiale di ordine n su m.
<BR>
<BR>
<BR>\"Chi si rilassa troppo finisce per cagarsi addosso.\" - HiTLeuLeR<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 12-10-2004 18:36 ]
<BR>[gcd(m, n)/n] · Bin(n, m) è un numero intero, ove Bin(n, m) denota - come al solito - il coefficiente binomiale di ordine n su m.
<BR>
<BR>
<BR>\"Chi si rilassa troppo finisce per cagarsi addosso.\" - HiTLeuLeR<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 12-10-2004 18:36 ]
- Franchifis
- Messaggi: 149
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa
<!-- BBCode Start --><I>No problem</I><!-- BBCode End -->, siamo qui per questo! Banalmente: gcd = greatest common divisor. Dannati inglesismi, vero? A buon <!-- BBCode Start --><I>rendering</I><!-- BBCode End -->...
<BR>
<BR>
<BR>\"Sedurre il prossimo a una buona opinione e poi credere con credulità a questa buona opinione: nessuno è più abile delle donne in questo pezzo di bravura.\" - F. W. Nietzsche, <!-- BBCode Start --><I>Al di là del bene e del male</I><!-- BBCode End -->
<BR>
<BR>
<BR>\"Sedurre il prossimo a una buona opinione e poi credere con credulità a questa buona opinione: nessuno è più abile delle donne in questo pezzo di bravura.\" - F. W. Nietzsche, <!-- BBCode Start --><I>Al di là del bene e del male</I><!-- BBCode End -->
uff.. finalmente! eppure a rivederlo adesso mi sembra una sciocchezza... cmq.
<BR>
<BR>Th.:
<BR>
<BR>(gcd(n, m)/n) * bin(n, m) = k con:
<BR>
<BR>n,m,k app. N e n >= m
<BR>
<BR>Dim.:
<BR>
<BR>Trascriviamo la formula del binomiale:
<BR>
<BR>
<BR>bin(n, m) = n! / (m! * (n - m)!)
<BR>
<BR>se semplifichiamo n! con m! otteniamo la produttoria da n a (n - m + 1).
<BR>
<BR>Trascriviamo quindi la formula iniziale:
<BR>
<BR>(gcd(n, m) / n) * ( n(n - 1).....(n - m + 1) ) / (n - m)!)
<BR>
<BR>
<BR>semplifichiamo ed eliminiamo la n dalle due frazioni.
<BR>
<BR>Nella seconda frazione, a numeratore abbiamo il prodotto di (n - m) numeri consecutivi e a denominatore abbiamo proprio (n - m)! (fattoriale) quindi il quoto e\' un numero naturale (va dimostrato pure questo? e\' banale...) che moltiplicato per gcd(n, m) da\' un altro numero naturale.
<BR>
<BR>c.v.d.
<BR>
<BR>mo\' mi merito sta birra!
<BR>
<BR>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: darko il 22-10-2004 09:43 ]
<BR>Mancava una parentesi<BR><BR>[ Questo Messaggio è stato Modificato da: darko il 22-10-2004 09:58 ]
<BR>
<BR>Th.:
<BR>
<BR>(gcd(n, m)/n) * bin(n, m) = k con:
<BR>
<BR>n,m,k app. N e n >= m
<BR>
<BR>Dim.:
<BR>
<BR>Trascriviamo la formula del binomiale:
<BR>
<BR>
<BR>bin(n, m) = n! / (m! * (n - m)!)
<BR>
<BR>se semplifichiamo n! con m! otteniamo la produttoria da n a (n - m + 1).
<BR>
<BR>Trascriviamo quindi la formula iniziale:
<BR>
<BR>(gcd(n, m) / n) * ( n(n - 1).....(n - m + 1) ) / (n - m)!)
<BR>
<BR>
<BR>semplifichiamo ed eliminiamo la n dalle due frazioni.
<BR>
<BR>Nella seconda frazione, a numeratore abbiamo il prodotto di (n - m) numeri consecutivi e a denominatore abbiamo proprio (n - m)! (fattoriale) quindi il quoto e\' un numero naturale (va dimostrato pure questo? e\' banale...) che moltiplicato per gcd(n, m) da\' un altro numero naturale.
<BR>
<BR>c.v.d.
<BR>
<BR>mo\' mi merito sta birra!
<BR>
<BR>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: darko il 22-10-2004 09:43 ]
<BR>Mancava una parentesi<BR><BR>[ Questo Messaggio è stato Modificato da: darko il 22-10-2004 09:58 ]
moio x la lyberta\'
darko, ho visto il tuo proof velocemente ma mi sembra contenga molti <!-- BBCode Start --><I>mistakes</I><!-- BBCode End -->!
<BR>
<BR>P.S.: Mi chiedo quando arriverà la sfuriata di HiTLeuLeR...
<BR>
<BR>
<BR>
<BR>P.S.: Mi chiedo quando arriverà la sfuriata di HiTLeuLeR...
<BR>
<BR>
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow
Tipo quando semplifichi n! per m!... Infatti: n*(n-1)*...*(m+1)*m! = n! e non n*(n-1)*...*(n-m+1)*m!. In questo modo ti esce l\'uguaglianza n*(n-1)*...*(n-m+1)/(n-m)! = n*(n-1)*...*(n-m+1)*/m!, valida solo per n = 2m.<BR><BR>[ Questo Messaggio è stato Modificato da: DB85 il 22-10-2004 16:14 ]
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-22 09:39, darko wrote:
<BR>[...] mo\' mi merito sta birra!
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Sì, ceeerto! Te ne meriteresti una cassa intera... sulla testa, però!!!
<BR>
<BR>
<BR>\"Ti consiglio d\'imbarcarti a bordo del primo treno bianco per Lourdes: chissà che non avvenga <!-- BBCode Start --><I>di nuovo</I><!-- BBCode End --> il miracolo...\" - HiTLeuLeR
<BR>On 2004-10-22 09:39, darko wrote:
<BR>[...] mo\' mi merito sta birra!
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Sì, ceeerto! Te ne meriteresti una cassa intera... sulla testa, però!!!
<BR>
<BR>
<BR>\"Ti consiglio d\'imbarcarti a bordo del primo treno bianco per Lourdes: chissà che non avvenga <!-- BBCode Start --><I>di nuovo</I><!-- BBCode End --> il miracolo...\" - HiTLeuLeR
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Simboli:
<BR>
<BR>a==b (m) a congruo b modulo m
<BR>[m/n]= parte intera del rapporto m/n
<BR>gcd(m,n)= (m<!-- BBCode Start --><B>,</B><!-- BBCode End -->n) = d (in futuro la virgola sarà in carattere normale)
<BR>Bin(m n) = (m n)
<BR>
<BR>Lemma 1
<BR>
<BR>m,n sono numeri naturali tali che m>n
<BR>Allora
<BR>(m,n) = m-[m/n]*n
<BR>
<BR>Dimostrazione:
<BR>
<BR>Consideriamo il seguente problema:
<BR>Detrminare il numero di quadratini, Q, attraversati dalla diagonale di un rettangolo di n*m quadratini unitari.
<BR>
<BR>Soluzione 1
<BR>
<BR>se m==0 (n) allora Q=m
<BR>
<BR>altrimenti
<BR>Q=([m/n]+1)*n il numero di quadratini attraversati dalla diagonale del rettangolo è uguale al numero di quadratini attraversati dalla diagonale del rettangolo omotetico a quello dato con rapporto di omotetia 1/n, moltiplicati per n.
<BR>
<BR>Soluzione 2
<BR>
<BR>se (m,n)=1 allora la diagonale non passa per nessun vertice di quadratini interni e dunque l\'attraversamento di ogni riga orizzontale di ogni riga verticale determinano il passaggio da un quadratino all\'altro, perciò:
<BR>Q=1 (quadratino di partenza) +(m-1)+(n-1)=m+n-1
<BR>
<BR>se (m,n)=d allora la diagonale passa per d-1 vertici di quadratini interni al rettangolo perciò al numero precedente occorre togliere d-1:
<BR>Q=m+n-d
<BR>
<BR>Confrontando le due soluzioni otteniamo la seguente identità:
<BR>
<BR>([m/n]+1)*n=m+n-d
<BR>da cui
<BR>d= m-[m/n]*n come volevasi dimostrare.
<BR>
<BR>Dimostrato questo lemma torniamo al problema originale cercando di dimostrare la proposizione data partendo da una nota identità e manipolandola con passaggi corretti:
<BR>
<BR>(m n)= m/n *(m-1 n-1)
<BR>
<BR>(m,n)*(m n)= m/n *(m-1 n-1) * (m,n)
<BR>
<BR>(m,n)/m *(m n)= (m,n)/n *(m-1 n-1)
<BR>
<BR>sostituendo nel membro di destra dell\'uguaglianza il lemma 1 otteniamo:
<BR>
<BR>(m,n)/m *(m n)= ((m-[m/n]*n)/n)*(m-1 n-1)
<BR>
<BR>(m,n)/m *(m n)= m/n*(m-1 n-1) - [m/n]*(m-1 n-1)
<BR>
<BR>(m,n)/m *(m n)= (m n) - [m/n]*(m-1 n-1)
<BR>
<BR>Come volevasi dimostrare a sinistra abbiamo il termine richiesto dal problema e a sinistra un numero naturale perchè differenza di due naturali.
<BR>Nice problem, bye. <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>a==b (m) a congruo b modulo m
<BR>[m/n]= parte intera del rapporto m/n
<BR>gcd(m,n)= (m<!-- BBCode Start --><B>,</B><!-- BBCode End -->n) = d (in futuro la virgola sarà in carattere normale)
<BR>Bin(m n) = (m n)
<BR>
<BR>Lemma 1
<BR>
<BR>m,n sono numeri naturali tali che m>n
<BR>Allora
<BR>(m,n) = m-[m/n]*n
<BR>
<BR>Dimostrazione:
<BR>
<BR>Consideriamo il seguente problema:
<BR>Detrminare il numero di quadratini, Q, attraversati dalla diagonale di un rettangolo di n*m quadratini unitari.
<BR>
<BR>Soluzione 1
<BR>
<BR>se m==0 (n) allora Q=m
<BR>
<BR>altrimenti
<BR>Q=([m/n]+1)*n il numero di quadratini attraversati dalla diagonale del rettangolo è uguale al numero di quadratini attraversati dalla diagonale del rettangolo omotetico a quello dato con rapporto di omotetia 1/n, moltiplicati per n.
<BR>
<BR>Soluzione 2
<BR>
<BR>se (m,n)=1 allora la diagonale non passa per nessun vertice di quadratini interni e dunque l\'attraversamento di ogni riga orizzontale di ogni riga verticale determinano il passaggio da un quadratino all\'altro, perciò:
<BR>Q=1 (quadratino di partenza) +(m-1)+(n-1)=m+n-1
<BR>
<BR>se (m,n)=d allora la diagonale passa per d-1 vertici di quadratini interni al rettangolo perciò al numero precedente occorre togliere d-1:
<BR>Q=m+n-d
<BR>
<BR>Confrontando le due soluzioni otteniamo la seguente identità:
<BR>
<BR>([m/n]+1)*n=m+n-d
<BR>da cui
<BR>d= m-[m/n]*n come volevasi dimostrare.
<BR>
<BR>Dimostrato questo lemma torniamo al problema originale cercando di dimostrare la proposizione data partendo da una nota identità e manipolandola con passaggi corretti:
<BR>
<BR>(m n)= m/n *(m-1 n-1)
<BR>
<BR>(m,n)*(m n)= m/n *(m-1 n-1) * (m,n)
<BR>
<BR>(m,n)/m *(m n)= (m,n)/n *(m-1 n-1)
<BR>
<BR>sostituendo nel membro di destra dell\'uguaglianza il lemma 1 otteniamo:
<BR>
<BR>(m,n)/m *(m n)= ((m-[m/n]*n)/n)*(m-1 n-1)
<BR>
<BR>(m,n)/m *(m n)= m/n*(m-1 n-1) - [m/n]*(m-1 n-1)
<BR>
<BR>(m,n)/m *(m n)= (m n) - [m/n]*(m-1 n-1)
<BR>
<BR>Come volevasi dimostrare a sinistra abbiamo il termine richiesto dal problema e a sinistra un numero naturale perchè differenza di due naturali.
<BR>Nice problem, bye. <IMG SRC="images/forum/icons/icon_wink.gif">