Ταυτότητα Βαντερμόντ

Στην συνδυαστική, η ταυτότητα Βαντερμόντ δίνει ότι για οποιοσδήποτε φυσικούς αριθμούς $\nu ,\mu \in \mathbb {N}$ και $0\leq \kappa \leq \min(\nu ,\mu )$,

${\binom {\nu +\mu }{\kappa }}=\sum _{\lambda =0}^{\kappa }{\binom {\nu }{\lambda }}{\binom {\mu }{\kappa -\lambda }},$

όπου ${\tbinom {x}{y}}$ ο διωνυμικός συντελεστής.

Η ταυτότητα παίρνει το όνομά της από τον Αλέξιος-Θεόφιλος Βαντερμόντ.

Παράδειγμα

Για $\nu =2$, $\mu =3$ και $\kappa =3$, η ταυτότητα Βαντερμόντ δίνει ότι:

${\binom {5}{3}}={\binom {2}{0}}{\binom {3}{3}}+{\binom {2}{1}}{\binom {3}{2}}+{\binom {2}{2}}{\binom {3}{1}},$

που ισχύει καθώς

$10=1\cdot 1+2\cdot 3+1\cdot 3.$

Ένας εναλλακτικός τρόπος να δούμε την ισότητα είναι να μετρήσουμε τους δυνατούς τρόπους να φτιάξουμε μία επιτροπή με $3$ άτομα από τα συνολικά $5$ άτομα (εκ των οποίων $2$ είναι άνδρες και $3$ γυναίκες).

Πλήθος ανδρών/Γυναικών	Οι επιτροπές	Πλήθος επιτροπών
$0$/$2$	${\color {red}\Gamma _{1}\Gamma _{2}\Gamma _{3}}$	1
$1$/$1$	${\color {blue}\mathrm {A} _{1}}{\color {red}\Gamma _{1}\Gamma _{2}}$ ${\color {blue}\mathrm {A} _{1}}{\color {red}\Gamma _{1}\Gamma _{3}}$ ${\color {blue}\mathrm {A} _{1}}{\color {red}\Gamma _{2}\Gamma _{3}}$ ${\color {blue}\mathrm {A} _{2}}{\color {red}\Gamma _{1}\Gamma _{2}}$ ${\color {blue}\mathrm {A} _{2}}{\color {red}\Gamma _{1}\Gamma _{3}}$ ${\color {blue}\mathrm {A} _{2}}{\color {red}\Gamma _{2}\Gamma _{3}}$	6
$2$/$0$	${\color {blue}\mathrm {A} _{1}\mathrm {A} _{2}}{\color {red}\Gamma _{1}}$ ${\color {blue}\mathrm {A} _{1}\mathrm {A} _{2}}{\color {red}\Gamma _{2}}$ ${\color {blue}\mathrm {A} _{1}\mathrm {A} _{2}}{\color {red}\Gamma _{3}}$	3

Αποδείξεις

Αλγεβρική απόδειξη

Θεωρούμε το πολυώνυμο $p(x)=(x+1)^{\nu +\mu }$. Από το διωνυμικό θεώρημα, ο συντελεστής του $x^{\kappa }$ είναι ${\tbinom {\nu +\mu }{\kappa }}$. Γράφοντας το $p(x)$ ως:

$p(x)=(x+1)^{\nu }\cdot (x+1)^{\mu }=\left(\sum _{\lambda _{1}=0}^{\nu }{\binom {\nu }{\lambda _{1}}}x^{\lambda _{1}}\right)\cdot \left(\sum _{\lambda _{2}=0}^{\mu }{\binom {\mu }{\lambda _{2}}}x^{\lambda _{2}}\right),$

o όρος $x^{\kappa }$ προκύπτει από τον πολλαπλασιασμό των $x^{\lambda _{1}}$ και $x^{\lambda _{2}}$ με $\lambda _{1}+\lambda _{2}=\kappa$. Συνεπώς, ο συντελεστής του $x^{\kappa }$ δίνεται από τον άθροισμα

$\sum _{\lambda _{1}=0}^{\kappa }{\binom {\nu }{\lambda _{1}}}{\binom {\mu }{\kappa -\lambda _{1}}}.$

Από το διωνυμικό θεώρημα στο $(x+1)^{\nu +\mu }$ αυτός ο συντελεστής είναι ίσος με ${\tbinom {\nu +\mu }{\kappa }}$, και έπεται το ζητούμενο.

Συνδυαστική απόδειξη

Μπορούμε να αποδείξουμε την ταυτότητα με την εξής ερμηνεία. Έστω ότι έχουμε $\nu$ άνδρες και $\mu$ γυναίκες και θέλουμε να φτιάξουμε μία επιτροπή αποτελούμενη από $\kappa$ άτομα. Από τον συνδυαστικό ορισμό των διωνυμικών συντελεστών, υπάρχουν ${\tbinom {\nu +\mu }{\kappa }}$ τρόποι να διαλέξουμε αυτά τα άτομα.

Ένας άλλος τρόπος να μετρήσουμε το πλήθος των επιτροπών είναι να μετρήσουμε τις ομάδες που έχουν $\lambda =0,1,\ldots ,\kappa$ άνδρες και να τις αθροίσουμε. Ξανά, από τον ορισμό των διωνυμικών συντελεστών, υπάρχουν ${\tbinom {\nu }{\lambda }}$ τρόποι να διαλέξουμε τους άνδρες της επιτροπής και ${\tbinom {\mu }{\kappa -\lambda }}$ τρόποι να διαλέξουμε τις γυναίκες. Επομένως, συνολικά υπάρχουν

$\sum _{\lambda =0}^{\kappa }{\binom {\nu }{\lambda }}\cdot {\binom {\mu }{\kappa -\lambda }}.$

Επειδή αυτές οι δύο τιμές μετράνε την ίδια ποσότητα, λαμβάνουμε τη ζητούμενη ταυτότητα.

Δείτε επίσης

• Διωνυμικό θεώρημα
• Υπεργεωμετρική κατανομή