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

μαθηματική ταυτότητα σχετική με τους διωνυμικούς συντελεστές
(Ανακατεύθυνση από Ταυτότητα Βαντερμόντε)

Στην συνδυαστική, η ταυτότητα Βαντερμόντ δίνει ότι για οποιοσδήποτε φυσικούς αριθμούς και ,[1]:168[2]:31

όπου ο διωνυμικός συντελεστής.

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

Παράδειγμα

Επεξεργασία

Για  ,   και  , η ταυτότητα Βαντερμόντ δίνει ότι:

 

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

 

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

Πλήθος ανδρών/Γυναικών Οι επιτροπές Πλήθος επιτροπών
 / 

 

1
 / 

 
 
 

 
 
 

6
 / 

 
 
 

3

Αποδείξεις

Επεξεργασία

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

Επεξεργασία

Θεωρούμε το πολυώνυμο  . Από το διωνυμικό θεώρημα, ο συντελεστής του   είναι  . Γράφοντας το   ως:

 

o όρος   προκύπτει από τον πολλαπλασιασμό των   και   με  . Συνεπώς, ο συντελεστής του   δίνεται από τον άθροισμα

 

Από το διωνυμικό θεώρημα στο   αυτός ο συντελεστής είναι ίσος με  , και έπεται το ζητούμενο.

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

Επεξεργασία

Μπορούμε να αποδείξουμε την ταυτότητα με την εξής ερμηνεία. Έστω ότι έχουμε   άνδρες και   γυναίκες και θέλουμε να φτιάξουμε μία επιτροπή αποτελούμενη από   άτομα. Από τον συνδυαστικό ορισμό των διωνυμικών συντελεστών, υπάρχουν   τρόποι να διαλέξουμε αυτά τα άτομα.

Ένας άλλος τρόπος να μετρήσουμε το πλήθος των επιτροπών είναι να μετρήσουμε τις ομάδες που έχουν   άνδρες και να τις αθροίσουμε. Ξανά, από τον ορισμό των διωνυμικών συντελεστών, υπάρχουν   τρόποι να διαλέξουμε τους άνδρες της επιτροπής και   τρόποι να διαλέξουμε τις γυναίκες. Επομένως, συνολικά υπάρχουν

 

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

Δείτε επίσης

Επεξεργασία

Παραπομπές

Επεξεργασία
  1. Graham, Ronald L.· Knuth, Donald E.· Patashnik, Oren (1997). Concrete mathematics : a foundation for computer science (2η έκδοση). Reading, Mass.: Addison-Wesley. ISBN 9780201558029. 
  2. Φωτάκης, Δ. «Συνδυαστική Απαρίθµηση» (PDF). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Εθνικό Μετσόβιο Πολυτεχνείο. Ανακτήθηκε στις 6 Αυγούστου 2022.