Cosa conta la formula?

[Tino]

Propongo un problema collegato in maniera involuta a quello di "indovina il seme".

Riuscite a trovare un modo "insiemistico" di dimostrare la seguente uguaglianza?

$\displaystyle \sum_{a+b=t} {2a \choose a} {2b \choose b} = 2^{2t}$,

dove $0 \leq a,b \leq t$.

Mi piacerebbe sapere cosa diamine sta contando questa formula pesca a oggetti tra 2a e b tra 2b con a+b=t, come se questo determinasse univocamente una sequenza binaria di lunghezza 2t. Ma come? Ci sto pensando da un po' senza risultati soddisfacenti.

[panurgo]

Riuscite a trovare un modo "insiemistico" di dimostrare la seguente uguaglianza?

$\displaystyle \sum_{a+b=t} {2a \choose a} {2b \choose b} = 2^{2t}$,

dove $0 \leq a,b \leq t$.

Cominciamo a riscrivere la sommatoria in modo da evidenziare che l'addendo dipende solo da due parametri

$\sum_{\script k=0}^{\script n}{F\left( n,k \right)} \/=\/ 4^{\script n}$

dove

$F\left( n,k \right) \/=\/ {{2k} \choose {k}}\/{{2n-2k} \choose {n-k}}$

quindi, utilizzando l'algoritmo di Zeilberger (vedi A = B) troviamo che

$S\left( n \right) \/=\/ \sum_{\script k=0}^{\script n}{F\left( n,k \right)}$

soddisfa la relazione ricorsiva

$S\left( n \/+\/ 1 \right) \/=\/ 4\/ S\left( n \right)$

dalla quale, unitamente alla condizione iniziale

$S\left( 0 \right) \/=\/ 1$

segue la tesi.

Mi piacerebbe sapere cosa diamine sta contando questa formula pesca a oggetti tra 2a e b tra 2b con a+b=t, come se questo determinasse univocamente una sequenza binaria di lunghezza 2t. Ma come? Ci sto pensando da un po' senza risultati soddisfacenti.

$2k \choose k$ conta i cammini minimi distinti su una griglia quadrata di lato $k$



e, ovviamente, $2n - 2k \choose n - k$ conta i cammini minimi distinti su una griglia quadrata di lato $n \/-\/ k$.
Una possibile interpretazione di $F\left( n,k \right)$ è che conti i cammini distinti di $2n$ passi suddivisi in due direzioni ortogonali (vedi figura)



qualunque cosa voglia dire...

[fabtor]

qualunque cosa voglia dire...

Umh... E se fosse una specie di rappresentazione grafica sul piano complesso C?

(ci voglio pensare un po' su, ma è la prima cosa che mi è venuta in mente leggendo la risposta del sempre eccellente Panurgo e quindi mi pareva un buon motivo per convogliare menti più brillanti della mia su questa possibile interpretazione fatta un po' intuitivamente o come avrebbe detto il mio vecchio prof. di matematica dell'università, e scusate il francesismo, "ad cazzum" ).
Ciao

[panurgo]

Io pensavo ad una cosa così



una sorta di convoluzione