una sommatoria non proprio banale:
dimostrare che
$ \displaystyle \sum_{k=0}^{n} \binom{2n-k}{n-k}2^k = 2^{2n} $
ah, i libri di analisi
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Contiamo i modi di metter in fila 2n palline che possono essere blu o rosse: Questi modi sono ovviamente $ 2^{2n} $.
Ora contiamole in un altro modo: Contiamo tutti i modi in cui le blu sono in maggioranza. Quindi le blu sono almeno n. diciamo che quando siamo arrivati all'(n+1)-esima pallina blu sono passate n-k palline rosse. Quindi abbiamo 2n-k posti dove mettere le palline e abbiamo n palline blu e quindi $ \binom {2n-k}n =\binom {2n-k}{n-k} $; il posto 2n-k+1-esimo è occupato da una pallina blu e gli altri k-1 posti possono essere scelti in $ 2^{k-1} $ modi. Quindi abbiamo che il numero di modi di mettere le palline con la maggioranza di blu dove le rosse prima della n+1-esima blu è:
$ \displaystyle \binom {2n-k}{n-k}2^{k-1} $
e quindi sommando con k che va da 1 a n (infatti le rosse possono essere da un minimo di 0 ad un massimo di n-1), otteniamo:
$ \displaystyle \sum_{k=1}^n \binom {2n-k}{n-k}2^{k-1} $
Ora a queste sommiamo i modi in cui la maggioranza di palline è rossa e i modi in cui sono uguali e quindi abbiamo:
$ \displaystyle 2^{2n}=2\sum_{k=1}^n \binom {2n-k}{n-k}2^{k-1}+\binom {2n}n $
cioè la tesi poichè il 2° membro è $ \sum_{k=0}^n \binom{2n-k}{n-k}2^k $.
Ora contiamole in un altro modo: Contiamo tutti i modi in cui le blu sono in maggioranza. Quindi le blu sono almeno n. diciamo che quando siamo arrivati all'(n+1)-esima pallina blu sono passate n-k palline rosse. Quindi abbiamo 2n-k posti dove mettere le palline e abbiamo n palline blu e quindi $ \binom {2n-k}n =\binom {2n-k}{n-k} $; il posto 2n-k+1-esimo è occupato da una pallina blu e gli altri k-1 posti possono essere scelti in $ 2^{k-1} $ modi. Quindi abbiamo che il numero di modi di mettere le palline con la maggioranza di blu dove le rosse prima della n+1-esima blu è:
$ \displaystyle \binom {2n-k}{n-k}2^{k-1} $
e quindi sommando con k che va da 1 a n (infatti le rosse possono essere da un minimo di 0 ad un massimo di n-1), otteniamo:
$ \displaystyle \sum_{k=1}^n \binom {2n-k}{n-k}2^{k-1} $
Ora a queste sommiamo i modi in cui la maggioranza di palline è rossa e i modi in cui sono uguali e quindi abbiamo:
$ \displaystyle 2^{2n}=2\sum_{k=1}^n \binom {2n-k}{n-k}2^{k-1}+\binom {2n}n $
cioè la tesi poichè il 2° membro è $ \sum_{k=0}^n \binom{2n-k}{n-k}2^k $.
Non sono molto ferrato in combinatoria: potresti chiarirmi qualche dubbio?
Che cos'è una combinazione semplice?perchè non è una disposizione o qualcos'altro?
Insomma mi sono perso in questo passaggio
$ \displaystyle \binom {2n-k}n $Simo_the_wolf ha scritto:Quindi abbiamo 2n-k posti dove mettere le palline e abbiamo n palline blu e quindi $ \binom {2n-k}n $;
Che cos'è una combinazione semplice?perchè non è una disposizione o qualcos'altro?
Insomma mi sono perso in questo passaggio
"Forse questo mondo è l'inferno di un'altro pianeta."
Aldous Huxley
Aldous Huxley
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Allora il binomiale si usa quando devi mettere k oggetti indistinguibili in n spazi. Procedi in questo modo:
Supponi che i tuoi oggetti siano delle palline numerate da 1 a k e gli spazi siano palline numerate da k+1 a n.
Ogni oggetto e ogni spazio lo metti dove vuoi in n! modi. Quante volte hai contato la stessa disposizione? k! modi di mettere le palline nei vari spazi prestabiliti e (n-k)! modi di mettere gli "spazi" negli altri posti. Quindi in totale:
$ \displaystyle \frac {n!}{k!(n-k)!} = \binom nk $
modi.
Se poi ci sono ad esempio a palline rosse , b palline blu e c palline verdi da disparre allora abbiamo analogamente
$ \displaystyle \frac {(a+b+c)!}{a!b!c!} $
modi di mettere le a+b+c palline.
Spero di essere stato il più chiaro possibile...
Supponi che i tuoi oggetti siano delle palline numerate da 1 a k e gli spazi siano palline numerate da k+1 a n.
Ogni oggetto e ogni spazio lo metti dove vuoi in n! modi. Quante volte hai contato la stessa disposizione? k! modi di mettere le palline nei vari spazi prestabiliti e (n-k)! modi di mettere gli "spazi" negli altri posti. Quindi in totale:
$ \displaystyle \frac {n!}{k!(n-k)!} = \binom nk $
modi.
Se poi ci sono ad esempio a palline rosse , b palline blu e c palline verdi da disparre allora abbiamo analogamente
$ \displaystyle \frac {(a+b+c)!}{a!b!c!} $
modi di mettere le a+b+c palline.
Spero di essere stato il più chiaro possibile...