4.4 Συνδυαστικές αποδείξεις ταυτοτήτων

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

Παράδειγμα 4.8   (Τρίγωνο του Pascal) Δείξτε την ταυτότητα

$${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}.$$ (4.7)

Το αριστερό μέλος μετράει τα $k$-μελή υποσύνολα του $[n]={\left\{{1,\ldots,n}\right\}}$. Αυτά όμως είναι δυο κατηγοριών: αυτά που περιέχουν το στοιχείο $n$ και τα υπόλοιπα. Το πλήθος αυτών που περιέχουν το $n$ είναι ${n-1 \choose k-1}$ αφού κάθε ένα από αυτά τα $k$-μελή υποσύνολα καθορίζεται μονοσήμαντα από την τομή του με το σύνολο $[n-1]={\left\{{1,\ldots,n-1}\right\}}$ που έχει μέγεθος $k-1$. Τα υπόλοιπα υποσύνολα επίσης καθορίζονται μονοσήμαντα από την τομή τους με το $[n-1]$, μόνο που αυτή τώρα έχει μέγεθος $k$, άρα το πλήθος τους είναι ${n-1 \choose k}$.

Παράδειγμα 4.9   Σε μια συγκέντρωση ο αριθμός των καλεσμένων που ανταλλάσσουν περιττές σε πλήθος χειραψίες είναι άρτιος.

Έστω $P_1,\ldots,P_n$ οι καλεσμένοι. Θεωρούμε το σύνολο των ζευγών $(P_i, P_j)$ τέτοια ώστε ο $P_i$ χαιρετάει τον $P_j$, και ας είναι $x_i$ ο αριθμός των χειραψιών που ανταλλάσσει ο $P_i$ και $y$ ο συνολικός αριθμός χειραψιών που ανταλλάσονται. Το πλήθος των ζευγών $(P_i, P_j)$ ισούται, από τη μια μεριά, με $\sum_{i=1}^n x_i$, και, από την άλλη, με $2y$, αφού σε κάθε χειραψία αντιστοιχούν ακριβώς δύο ζευγάρια $(P_i, P_j)$ και $(P_j, P_i)$. Έτσι έχουμε

$$2y = \sum_{i=1}^n x_i$$

άρα το πλήθος των περιττών $x_i$ είναι αναγκαστικά άρτιο.

Παράδειγμα 4.10   Για $n_1, n_2 \ge 0$ ισχύει

$$\sum_{k=0}^m {n_1 \choose k} {n_2 \choose m-k} = {n_1+n_2 \choose m}, (m \le \min{\left\{{n_1,n_2}\right\}}).$$

Δεξιά μετράμε τα υποσύνολα μεγέθους $m$ του $[n_1+n_2]$. Βάφουμε τα $n_1$ αντικείμενα άσπρα και τα άλλα μαύρα. Τα υποσύνολα μεγέθους $m$ που μας ενδιαφέρουν χωρίζονται στις $m+1$ σε πλήθος κατηγορίες $C_k$, $k=0,\ldots,m$. Η κατηγορία $C_k$ περιλαμβάνει όλα τα $m$-μελή υποσύνολα του $[n_1+n_2]$ που περιέχουν ακριβώς $k$ άσπρα. Προφανώς έχουμε ${\left\vert{C_k}\right\vert} = {n_1 \choose k}{n_2 \choose m-k}$ αφού για να φτιάξουμε ένα υποσύνολα κατηγορίας $C_k$ πρέπει να επιλέξουμε $k$ άσπρα και τα υπόλοιπα $n-k$ μαύρα. Άρα το αριστερό μέλος της ισότητας είναι ίσο με $\sum_{k=0}^m {\left\vert{C_k}\right\vert}$.

Παράδειγμα 4.11   Για κάθε $n\ge 2$ ισχύει:

$${2n \choose 2} = 2{n \choose 2} + n^2.$$

Αριστερά μετράμε διμελή υποσύνολα του $[2n]$. Έστω ότι χρωματίζουμε $n$ από τα $2n$ αντικείμενα σε άσπρα και τα άλλα μαύρα. Τα διμελή υποσύνολα του $[2n]$ είναι τριών τύπων: (Α) δύο στοιχεία άσπρα, (Β) δύο στοιχεία μαύρα, (Γ) ένα άσπρο κι ένα μαύρο. Τα υποσύνολα τύπου (Α) είναι ${n \choose 2}$ σε πλήθος αφού διαλέγουμε δύο από τα $n$ άσπρα. Τόσα είναι και τα υποσύνολα τύπου (Β). Τα σύνολα τύπου (Γ) είναι σε πλήθος $n\cdot n$, μια και πρέπει να διαλέξουμε ένα από $n$ άσπρα και ένα από $n$ μαύρα. Το σύνολο για τις τρεις κατηγορίες συνόλων εμφανίζεται στο δεξί μέλος.

Παράδειγμα 4.12   Δείξτε ότι

$$n2^{n-1} = \sum_{k=1}^n k{n \choose k}$$ (4.8)

(δείτε επίσης το Παράδειγμα 4.6) αριθμώντας με δύο διαφορετικούς τρόπους τα ζεύγη $(x,M)$ τέτοια ώστε $x \in M \subseteq [n]$.

Υπάρχουν ${n \choose k}$ σύνολα $M \subseteq [n]$ με μέγεθος $k$, και για κάθε ένα από αυτά μπορούμε να επιλέξουμε ως $x$ οποιοδήποτε από τα $k$ στοιχεία του, άρα το πλήθος των ζευγών $(x,M)$ τέτοια ώστε $x \in M \subseteq [n]$ ισούται με το δεξί μέλος της (4.8).

Όμως τα ζεύγη αυτά μπορούν να αριθμηθούν επιλέγοντας πρώτα το $x$ και μετά επιλέγοντας τα υπόλοιπα στοιχεία του $M$, το σύνολο δηλ. $M\setminus{\left\{{x}\right\}}$. Όμως όλα τα σημεία του $[n]$ εκτός το $x$ συμμετέχουν στον καθορισμό του $M\setminus{\left\{{x}\right\}}$, και άρα οι δυνατότητες γι' αυτό είναι $2^{n-1}$, άρα οι δυνατότητες για τα ζεύγη είναι $n2^{n-1}$, που είναι το αριστερό μέλος.

Άσκηση 4.20   Αποδείξτε με συνδυαστικό επιχείρημα ότι αν $0 \le i \le k \le n$ τότε ισχύει

$${n \choose i} {n-i \choose k-i} = {k \choose i}{n \choose k}.$$

Άσκηση 4.21   Αποδείξτε με συνδυαστικό επιχείρημα την ταυτότητα

$${n \choose k} = \sum_{i=k}^n {i-1 \choose k-1}.$$

Υπόδειξη: Πόσα υποσύνολα του $[n]$ μεγέθους $k$ υπάρχουν τ.ώ. το μεγαλύτερο στοιχείο τους να είναι το $i$;

Άσκηση 4.22   Αν $n, m, k_1, \ldots, k_m$ είναι μη αρνητικοί ακέραιοι τ.ώ. $k_1+\cdots+k_m=n$ δείξτε με συνδυαστικό επιχείρημα ότι ισχύει

$${n \choose k_1, k_2, \ldots, k_m} = \sum_{i=1}^m {n-1 \choose k_1, \ldots, k_{i-1},(k_i-1), k_{i+1}, \ldots,k_m}.$$

Άσκηση 4.23   Αποδείξτε με συνδυαστικό επιχείρημα την ταυτότητα

$${0 \choose m} + {1 \choose m} + \cdots + {n \choose m} = {n+1 \choose m+1}$$

όπου $0 \le m \le n$. (Θυμηθείτε ότι οι διωνυμικοί συντελεστές ${a \choose b}$ με $a<b$ ισούνται με 0.)