Ancora binomiali

[Simo_the_wolf]

Posto che $ \binom ab =0 $ se $ b(a-b)<0 $ dire quanto è:

$ \displaystyle \sum_{k \in Z} \binom nk \binom m{k+a} $

con $ -n<a<m $

[edriv]

Dai che è carino... una volta fatta la fatica di leggere la formula.

Abbiamo un insieme di (m+n) elementi. Contiamo i sottoinsiemi di (m-a) elementi.

Primo modo
Beh, sono $ \displaystyle {m+n \choose m-a} $

Secondo modo
Dividiamo i sottoinsiemi di m-a elementi secondo il criterio: Quanti elementi abbiamo scelto tra i primi n?. Se la risposta a questa domanda è k, allora:
- gli elementi tra i primi n li posso scegliere in $ ~ n \choose k $ modi.
- gli elementi da n+1 a n+m devono essere (m-a) - k, quindi li scelgo in $ ~ {m \choose m-a-k} $, che è uguale a $ ~ {m \choose a+k} $ se al posto di scegliere quelli da mettere dentro, scelgo quelli da lasciare fuori.

E' chiaro a ogni scelta di un sottoinsieme di m-a elementi tra tutti gli m+n corrisponde ad un'unica coppia di scelte (quali elementi tra i primi n, quali elementi tra n+1 ed m), e viceversa.

Questo dimostra che:
$ \displaystyle \sum {n \choose k} {m \choose a+k} = {m+n \choose m-a} $.