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

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

$(\genfrac{}{}{0ex}{}{\nu +\mu }{\kappa })=\sum _{\lambda =0}^{\kappa }(\genfrac{}{}{0ex}{}{\nu }{\lambda })(\genfrac{}{}{0ex}{}{\mu }{\kappa -\lambda }),$

όπου $(\genfrac{}{}{0ex}{}{x}{y})$ ο διωνυμικός συντελεστής.

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

Παράδειγμα

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

$(\genfrac{}{}{0ex}{}{5}{3})=(\genfrac{}{}{0ex}{}{2}{0})(\genfrac{}{}{0ex}{}{3}{3})+(\genfrac{}{}{0ex}{}{2}{1})(\genfrac{}{}{0ex}{}{3}{2})+(\genfrac{}{}{0ex}{}{2}{2})(\genfrac{}{}{0ex}{}{3}{1}),$

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

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

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

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

Αποδείξεις

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

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

$p(x)=(x+1{)}^{\nu }\cdot (x+1{)}^{\mu }=\left(\sum _{{\lambda }_1=0}^{\nu }(\genfrac{}{}{0ex}{}{\nu }{{\lambda }_1})x^{{\lambda }_1}\right)\cdot \left(\sum _{{\lambda }_2=0}^{\mu }(\genfrac{}{}{0ex}{}{\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 }(\genfrac{}{}{0ex}{}{\nu }{{\lambda }_1})(\genfrac{}{}{0ex}{}{\mu }{\kappa -{\lambda }_1}).$

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

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

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

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

$\sum _{\lambda =0}^{\kappa }(\genfrac{}{}{0ex}{}{\nu }{\lambda })\cdot (\genfrac{}{}{0ex}{}{\mu }{\kappa -\lambda }).$

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

Δείτε επίσης

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