OliForum Matematico

una sommatoria non proprio banale:

dimostrare che
$ \displaystyle \sum_{k=0}^{n} \binom{2n-k}{n-k}2^k = 2^{2n} $

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 $.

Non sono molto ferrato in combinatoria: potresti chiarirmi qualche dubbio?

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 $;

$ \displaystyle \binom {2n-k}n $
Che cos'è una combinazione semplice?perchè non è una disposizione o qualcos'altro?
Insomma mi sono perso in questo passaggio

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...