Στοιχειώδης συνδυαστική και το διώνυμο του Νεύτωνα

Οι αρχές της απαρίθμησης

Η μέτρηση των στοιχείων ενός πεπερασμένου συνόλου είναι η πιο στοιχειώδης πράξη της αριθμητικής, όσο το σύνολο μπορεί να διατρεχθεί στοιχείο προς στοιχείο. Ωστόσο, όταν τα στοιχεία είναι οι τρόποι να γίνει μια σύνθετη επιλογή, όπως να τοποθετηθούν δέκα βιβλία σε ένα ράφι ή να επιλεγούν τρεις εκπρόσωποι ανάμεσα σε τριάντα πρόσωπα, η απαρίθμηση γίνεται ανέφικτη, και το πλήθος προκύπτει αν αναλύσουμε την επιλογή σε μέρη ή σε στάδια. Όλη η στοιχειώδης συνδυαστική στηρίζεται σε δύο αρχές, που αποδεικνύονται από έναν ακριβή ορισμό του τι σημαίνει μετρώ.

Να μετρήσουμε τα στοιχεία ενός συνόλου σημαίνει να τα αριθμήσουμε: να αντιστοιχίσουμε σε κάθε αριθμό από τον $1$ έως τον $n$ ένα στοιχείο, χωρίς να επαναλάβουμε κανένα και χωρίς να παραλείψουμε κανένα. Λέμε ότι ένα σύνολο $A$ έχει $n$ στοιχεία, με $n$ φυσικό, όταν υπάρχει μια αμφιμονοσήμαντη αντιστοιχία από το σύνολο $\{1, 2, \ldots, n\}$ στο $A$, δηλαδή μια συνάρτηση που στέλνει διαφορετικούς αριθμούς σε διαφορετικά στοιχεία και φτάνει σε όλα τα στοιχεία του $A$· το κενό σύνολο έχει $0$ στοιχεία, και ένα σύνολο είναι πεπερασμένο αν είναι κενό ή έχει $n$ στοιχεία για κάποιον φυσικό $n$. Οι αμφιμονοσήμαντες αντιστοιχίες, η σύνθεσή τους και η αντίστροφή τους μελετώνται στο μάθημα για τα σύνολα, τις σχέσεις και τις συναρτήσεις.

Γεγονός που δεχόμαστε χωρίς απόδειξη (πλήθος στοιχείων). Δεχόμαστε χωρίς απόδειξη ότι το πλήθος των στοιχείων ενός πεπερασμένου συνόλου είναι καλά ορισμένο: ένα σύνολο δεν μπορεί να έχει συγχρόνως $m$ στοιχεία και $n$ στοιχεία αν $m \neq n$. Δεχόμαστε επίσης ότι κάθε υποσύνολο ενός πεπερασμένου συνόλου είναι πεπερασμένο.

Και τα δύο γεγονότα αποδεικνύονται με επαγωγή ως προς $n$· το πρώτο είναι, στην ουσία του, η αρχή του περιστερώνα, σύμφωνα με την οποία δεν υπάρχει συνάρτηση που να στέλνει τους $n + 1$ αριθμούς του $\{1, \ldots, n + 1\}$ σε διαφορετικούς αριθμούς του $\{1, \ldots, n\}$. Οι αποδείξεις τους είναι μακροσκελείς και δεν προσφέρουν ιδέες που χρησιμοποιούνται αργότερα, και γι' αυτό τα δεχόμαστε. Χωρίς το πρώτο, η έκφραση «το πλήθος των στοιχείων» δεν θα είχε νόημα, και μια συνδυαστική απόδειξη, που μετρά το ίδιο σύνολο με δύο τρόπους, δεν θα μπορούσε να συμπεράνει ότι τα δύο αποτελέσματα είναι ίσα.

Με επαγωγή ως προς το πλήθος των μερών, η αρχή επεκτείνεται σε οποιοδήποτε πεπερασμένο πλήθος συνόλων χωρίς κοινά στοιχεία ανά δύο: η ένωση των $A_1, \ldots, A_r$, με $n_1, \ldots, n_r$ στοιχεία, έχει $n_1 + \cdots + n_r$ στοιχεία, επειδή η ένωση των $r + 1$ πρώτων συνόλων είναι η ένωση των $r$ πρώτων με το τελευταίο, που δεν έχει κοινά στοιχεία με αυτά. Από αυτήν συνάγεται η δεύτερη αρχή, που μετρά τις επιλογές που γίνονται σε στάδια.

Με τον ίδιο τρόπο, με επαγωγή ως προς το πλήθος των σταδίων, η πολλαπλασιαστική αρχή επεκτείνεται σε οποιοδήποτε πεπερασμένο πλήθος σταδίων: μια επιλογή σε $r$ στάδια, που μπορούν να γίνουν με $n_1, n_2, \ldots, n_r$ τρόπους αντίστοιχα, μπορεί να γίνει με $n_1 n_2 \cdots n_r$ τρόπους. Για παράδειγμα, στο δεκαδικό σύστημα που μελετήθηκε στο μάθημα για τα θεσιακά συστήματα αρίθμησης υπάρχουν $9 \cdot 10 \cdot 10 = 900$ τριψήφιοι αριθμοί, επειδή το πρώτο ψηφίο δεν μπορεί να είναι $0$ και τα άλλα δύο είναι ελεύθερα. Πρέπει να σημειωθεί ότι η πολλαπλασιαστική αρχή απαιτεί το πλήθος των επιλογών κάθε σταδίου να μην εξαρτάται από όσα επιλέχθηκαν πριν, ακόμη κι αν οι ίδιες οι επιλογές εξαρτώνται· αν αυτή η συνθήκη δεν ισχύει, διακρίνουμε περιπτώσεις στις οποίες ισχύει και προσθέτουμε τα αποτελέσματά τους με την αρχή του αθροίσματος.

Τα διαδοχικά στάδια μιας επιλογής αναπαριστώνται με ένα δενδροδιάγραμμα: από ένα αρχικό σημείο, τη ρίζα, ξεκινούν τόσα κλαδιά όσες επιλογές έχει το πρώτο στάδιο· από το άκρο κάθε κλαδιού, τόσα όσες επιλογές έχει το δεύτερο, και ούτω καθεξής. Κάθε διαδρομή από τη ρίζα ως ένα τελικό άκρο, ή φύλλο, είναι μια πλήρης επιλογή, και η πολλαπλασιαστική αρχή μετρά τα φύλλα χωρίς να τα σχεδιάσει.