Identità di Vandermonde

In combinatoria, l'identità di Vandermonde (o convoluzione di Vandermonde) è la seguente identità riguardante i coefficienti binomiali:

${\displaystyle {m n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}}$

per ogni ${\displaystyle r}$, ${\displaystyle m}$, ${\displaystyle n}$ interi non negativi. L'identità deve il suo nome a Alexandre-Théophile Vandermonde (1772), sebbene fosse già conosciuta nel 1303 dal matematico cinese Zhu Shijie.

Si può generalizzare l'identita di Vandermonde in diversi modi, come ad esempio la seguente versione:

${\displaystyle {n_{1} \dots n_{p} \choose m}=\sum _{k_{1} \cdots k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}}$.

Dimostrazioni

Dimostrazione algebrica

In generale, il prodotto di due polinomi, di gradi ${\displaystyle m}$ e ${\displaystyle n}$ rispettivamente, è dato da

${\displaystyle {\biggl (}\sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{j}{\biggr )}=\sum _{r=0}^{m n}{\biggl (}\sum _{k=0}^{r}a_{k}b_{r-k}{\biggr )}x^{r},}$

dove si utilizza la convenzione per cui ${\displaystyle a_{i}=0}$ per tutti gli interi ${\displaystyle i>m}$, e ${\displaystyle b_{j}=0}$ se ${\displaystyle j>n}$. Per il teorema binomiale,

${\displaystyle (1 x)^{m n}=\sum _{r=0}^{m n}{m n \choose r}x^{r}.}$

Utilizzando lo sviluppo del binomio anche per gli esponenti ${\displaystyle m}$ e ${\displaystyle n}$, insieme alla precedente formula sul prodotto fra polinomi, si ottiene

${\displaystyle {\begin{aligned}\sum _{r=0}^{m n}{m n \choose r}x^{r}&=(1 x)^{m n}\\&=(1 x)^{m}(1 x)^{n}\\&={\biggl (}\sum _{i=0}^{m}{m \choose i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}{n \choose j}x^{j}{\biggr )}\\&=\sum _{r=0}^{m n}{\biggl (}\sum _{k=0}^{r}{m \choose k}{n \choose r-k}{\biggr )}x^{r},\end{aligned}}}$

dove la precedente convenzione per i coefficienti dei polinomi concorda con la definizione dei coefficienti binomiali, poiché entrambi valgono zero per ${\displaystyle i>m}$ e ${\displaystyle j>n}$.

Confrontando i coefficienti di ${\displaystyle x^{r}}$, si ricava l'identità di Vandermonde per ogni ${\displaystyle 0\leq r\leq m n}$. Per ${\displaystyle r}$ maggiori, entrambi i membri dell'identità sono zero per via della definizione del coefficiente binomiale.

Dimostrazione combinatoria

L'identità di Vandermonde ammette anche una dimostrazione combinatoria mediante doppio conteggio, come segue. Si supponga una commissione composta da ${\displaystyle m}$ uomini e ${\displaystyle n}$ donne. In quanti modi si può formare un sottocomitato di ${\displaystyle r}$ persone? La risposta è

${\displaystyle {m n \choose r}.}$

La soluzione è anche uguale alla somma su ${\displaystyle k}$ del numero di gruppi composti da ${\displaystyle k}$ uomini e ${\displaystyle r-k}$ donne:

${\displaystyle \sum _{k=0}^{r}{m \choose k}{n \choose r-k}.}$

Dimostrazione geometrica

Si prenda una griglia rettangolare di ${\displaystyle r\cdot (m n-r)}$ quadrati. Ci sono esattamente

${\displaystyle {\binom {r (m n-r)}{r}}={\binom {m n}{r}}}$

percorsi dal vertice in basso a sinistra a quello in alto a destra, muovendosi soltanto a destra o verso l'alto. Infatti, si devono compiere in qualsiasi ordine ${\displaystyle r}$ movimenti a destra e ${\displaystyle m n-r}$ verso l'alto, e la lunghezza totale del percorso è ${\displaystyle m n}$. Si indichi il vertice in basso a sinistra come ${\displaystyle (0,0)}$.

In modo analogo, ci sono ${\displaystyle {\binom {m}{k}}}$ cammini da ${\displaystyle (0,0)}$ a ${\displaystyle (k,m-k)}$, e ${\displaystyle {\binom {n}{r-k}}}$ percorsi da ${\displaystyle (k,m-k)}$ a ${\displaystyle (r,m n-r)}$. Perciò ci sono

${\displaystyle {\binom {m}{k}}{\binom {n}{r-k}}}$

percorsi che partono da ${\displaystyle (0,0)}$, finiscono in ${\displaystyle (r,m n-r)}$ e passano per ${\displaystyle (k,m-k)}$. Quest'ultimi sono solo un sottoinsieme di tutti i possibili cammini tra i due vertici opposti, quindi si somma da ${\displaystyle k=0}$ a ${\displaystyle k=r}$ (dal momento che il punto ${\displaystyle (k,m-k)}$ deve essere all'interno della griglia) e si ottiene l'identità di Vandermonde.

Generalizzazioni

Identità di Vandermonde generalizzata

Si può generalizzare l'identità come segue:

${\displaystyle \sum _{k_{1} \cdots k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}={n_{1} \dots n_{p} \choose m}.}$

Questa versione si può ottenere attraverso la derivazione algebrica di prima ma in cui si utilizzano più di due polinomi, oppure mediante un semplice ragionamento di doppio conteggio.

Da una parte, si scelgono ${\displaystyle \textstyle k_{1}}$ elementi dal primo dei ${\displaystyle p}$ insiemi e composto ${\displaystyle \textstyle n_{1}}$ elementi, poi ${\displaystyle \textstyle k_{2}}$ dal secondo insieme, e così via, fino a un totale di ${\displaystyle m}$ oggetti scelti. Pertanto, nel membro di sinistra si scelgono ${\displaystyle \textstyle m}$ elementi su ${\displaystyle \textstyle n_{1} \dots n_{p}}$, che è esattamente il membro destro dell'uguaglianza.

Identità di Chu–Vandermonde

L'identità si può generalizzare anche per argomenti non interi. In questo caso, è nota come identità di Chu–Vandermonde e assume la forma

${\displaystyle {s t \choose n}=\sum _{k=0}^{n}{s \choose k}{t \choose n-k},}$

con ${\displaystyle s}$ e ${\displaystyle t}$ numeri complessi arbitrari e ${\displaystyle n}$ un intero non negativo. Si può ricavare l'identità basandosi sulla precedente dimostrazione algebrica, moltiplicando fra loro le serie binomiali di ${\displaystyle (1 x)^{s}}$ e ${\displaystyle (1 x)^{t}}$, e successivamente comparando i termini della serie di ${\displaystyle (1 x)^{s t}}$.

L'identità si può riscrivere in termini del simbolo di Pochhammer decrescente come

${\displaystyle (s t)_{n}=\sum _{k=0}^{n}{n \choose k}(s)_{k}(t)_{n-k},}$

in cui si riconosce chiaramente una variante umbrale del teorema binomiale. L'identità di Chu–Vandermonde può anche essere vista come un caso speciale del teorema ipergeometrico di Gauss, il quale afferma che

${\displaystyle \;_{2}F_{1}(a,b;c;1)={\frac {\Gamma (c)\Gamma (c-a-b)}{\Gamma (c-a)\Gamma (c-b)}},}$

dove ${\displaystyle \;_{2}F_{1}}$ è la funzione ipergeometrica e ${\displaystyle \Gamma (n 1)=n!}$ è la funzione Gamma. In particolare, si ottiene l'identità di Chu–Vandermonde ponendo ${\displaystyle a=-n}$ e applicando liberamente la relazione

${\displaystyle {n \choose k}=(-1)^{k}{k-n-1 \choose k}.}$

Un'ulteriore generalizzazione è data dalla seguente identità di Rothe–Hagen:

${\displaystyle \sum _{k=0}^{n}{\frac {x}{x kz}}{x kz \choose k}{\frac {y}{y (n-k)z}}{y (n-k)z \choose n-k}={\frac {x y}{x y nz}}{x y nz \choose n},}$

per ogni ${\displaystyle x}$, ${\displaystyle y}$ e ${\displaystyle z}$ complessi.

La distribuzione ipergeometrica di probabilità

Quando si dividono entrambi i membri per l'espressione a destra, cosicché la somma è 1, allora i termini della sommatoria possono essere interpretati come probabilità. La distribuzione di probabilità risultante è quella distribuzione ipergeometrica, cioè quella che descrive l'estrazione senza reinserimento di alcune palline, perdenti o vincenti, da un'urna.

Note

Bibliografia

• Richard Askey, Orthogonal polynomials and special functions, Regional Conference Series in Applied Mathematics, vol. 21, Philadelphia, PA, SIAM, 1975, pp. viii 110.

Voci correlate

• Coefficiente binomiale
• Triangolo di Tartaglia
• Teorema binomiale
• Distribuzione binomiale