4.1 Διαμερίσεις και συνδυασμοί με επανάθεση

Ας συμβολίσουμε με $P(n,r)$ το πλήθος των τρόπων με τους οποίους μπορούμε να γράψουμε τον φυσικό αριθμό $n$ ως άθροισμα $r$ μη αρνητικών ακεραίων $x_1,\ldots,x_r$:

$$n = x_1 + \cdots + x_r.$$

Για παράδειγμα, αν $n=3$ και $r=2$ οι τρόποι αυτοί είναι οι

$$3 = 3 + 0 = 2 + 1 = 1 + 2 = 0 + 3$$ (4.1)

και άρα $P(3,2)=4$. Η σειρά των προσθετέων $x_1,\ldots,x_r$ έχει σημασία. Την ποσότητα $P(n,r)$ την ονομάζουμε πλήθος διαμερίσεων του $n$ σε $r$ κομμάτια. Παρατηρήστε ότι δεν απαιτούμε το $r$ να είναι $\le n$ αφού το μέγεθος των κομματιών μπορεί να είναι και 0.

Θεώρημα 4.1   Αν $n \ge 0$ και $r\ge 0$ τότε ισχύει

$$P(n,r) = {n+r-1 \choose n}={n+r-1 \choose r-1}.$$ (4.2)

Απόδειξη. Παριστάνουμε τον αριθμό $n$ σα $n$ μπάλες στη σειρά και την τυχούσα διαμέριση του $n$, δηλ. τον τυχόντα τρόπο να γράψουμε $n=x_1+\cdots+x_r$, σαν ένα χωρισμό αυτής της σειράς από μπάλες με $r-1$ τοιχώματα (δείτε Σχήμα 4.1).

Σχήμα 4.1: Χωρίζοντας $n=11$ μπάλες σε $r=10$ ομάδες με 9 ενδιάμεσα τοιχώματα

Η τιμή του $x_1$ βρίσκεται αν μετρήσουμε πόσες μπάλες υπάρχουν από το $-\infty$ έως το πρώτο τοίχωμα, το $x_2$ αν μετρήσουμε τις μπάλες από το πρώτο έως το δεύτερο τοίχωμα, κλπ. Τέλος το $x_r$ βρίσκεται αν μετρήσουμε τις μπάλες από το τελευταίο (υπ' αριθμόν $r-1$) τοίχωμα έως το $+\infty$.

Άρα, για να μετρήσουμε το πλήθος των διαμερίσεων $P(n,r)$ αρκεί να μετρήσουμε πόσα διαφορετικά σχήματα σαν και αυτό του Σχήματος 4.1 υπάρχουν, αφού είναι φανερό ότι σε κάθε τέτοιο σχήμα αντιστοιχεί και μια διαφορετική διαμέριση, και αντίστροφα.

Με ποια διαδικασία μπορούμε λοιπόν να κατασκευάσουμε μονοσήμαντα ένα τέτοιο σχήμα; Το κάνουμε ως εξής: βάζουμε πρώτα στη σειρά $n+r-1$ αντικείμενα και κατόπιν ονομάζουμε τα $n$ από αυτά μπάλες και τα υπόλοιπα $r-1$ τοιχώματα. Αυτό μπορεί να γίνει ακριβώς με ${n+r-1 \choose n}$ τρόπους. Η δεύτερη ισότητα μέσα στο συμπέρασμα του Θεωρήματος 4.1 είναι απλή συνέπεια της ταυτότητας ${a \choose b} = {a \choose a-b}$ (δείτε την Άσκηση 3.37). $\qedsymbol$

Για παράδειγμα σύμφωνα με το Θεώρημα 4.1 ισχύει $P(3,2)={3+2-1 \choose 3} = {4 \choose 3} = 4$ το οποίο συμφωνεί με την (4.1).

Άσκηση 4.1   Βρείτε όλες τις διαμερίσεις του 4 σε 3 κομμάτια.

Πέρα από τη σημασία που έχει το ίδιο το πρόβλημα του να μετρήσουμε το πλήθος των διαμερίσεων του $n$ σε $r$ κομμάτια, το ερώτημα αποκτά μεγαλύτερη σημασία γιατί είναι ένας ισοδύναμος τρόπος του να ρωτήσουμε το εξής:

Με πόσους τρόπους μπορούμε να επιλέξουμε $k$ από $n$ στοιχεία όταν κάθε στοιχείο από τα $n$ μπορεί να επιλεγεί ένα απεριόριστο αριθμό από φορές, και όταν δε μας ενδιαφέρει η σειρά των επιλεγέντων στοιχείων;

Ένας ισοδύναμος τρόπος να θέσουμε το ίδιο ερώτημα είναι ο ακόλουθος. Έχουμε ένα σάκο που έχει μέσα $n$ μπάλες. Οι μπάλες φέρουν η κάθε μια τον αριθμό της. Επαναλαμβάνουμε $k$ φορές την πράξη:

Παίρνουμε μια μπάλα από το σάκο και γράφουμε σ' ένα χαρτί τον αριθμό της. Έπειτα επανατοποθετούμε τη μπάλα στο σάκο.

Στο τέλος παρατηρούμε τους $k$ αριθμούς που γράψαμε, χωρίς να μας ενδιαφέρει η σειρά τους. Πόσα είναι τα δυνατά διαφορετικά αποτελέσματα; Από αυτή την εναλλακτική περιγραφή προκύπτει και το όνομα συνδυασμοί $n$ στοιχείων ανά $k$ με επανάθεση. Το πλήθος αυτών των συνδυασμών συμβολίζεται με ${\left\langle{{n} \atop {k}}\right\rangle}$.

Παράδειγμα 4.1   Οι συνδυασμοί του συνόλου ${\left\{{A,B}\right\}}$ ανά 3 με επανάθεση είναι οι

$$AAA, AAB, ABB, BBB.$$

Για παράδειγμα, ο συνδυασμός $ABB$ θεωρείται ίδιος με τον $BAB$ μια και τα στοιχεία διαφέρουν μόνο στη σειρά εμφάνισης.

Άσκηση 4.2   Δείξτε ότι για κάθε $n$ ισχύει ${\left\langle{{n} \atop {1}}\right\rangle} = n$. Επίσης ότι, για $n\ge 2$, ισχύει ${\left\langle{{n} \atop {2}}\right\rangle} = n+{n \choose 2}$.

Άσκηση 4.3   Βρείτε το $X$ στην ισότητα

$${\left\langle{{n} \atop {3}}\right\rangle} = {n \choose 3} + X.$$

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

Ομοίως σκεπτόμενοι βρείτε τη διαφορά ${\left\langle{{n} \atop {4}}\right\rangle}-{n \choose 4}$.

Στο τέλος αυτής της διαδικασίας επιλογής $k$ στοιχείων με επανάθεση έχουμε στα χέρια μας $k$ αριθμούς, όχι κατ' ανάγκη διαφορετικούς μεταξύ τους, κάθε ένας από τους οποίους ανήκει στο σύνολο ${\left\{{1,\ldots,n}\right\}}$. Έστω $x_i$, $i=1,\ldots,n$, το πλήθος αυτών των αριθμών που είναι ίσοι με $i$. Επειδή δε μας ενδιαφέρει η σειρά που εμφανίζεται κάθε ένα από τα νούμερα που επιλέγουμε, αλλά μόνο το πόσες φορές εμφανίζεται, γίνεται φανερό ότι

$$x_1+\cdots+x_n=k$$ (4.3)

και ότι κάθε διαφορετικό αποτέλεσμα της επιλογής με επανάθεση αντιστοιχεί και σε μια διαφορετική $n$-άδα $x_1,\ldots,x_n$ που ικανοποιεί την (4.3). Έχουμε έτσι αποδείξει το ακόλουθο.

Θεώρημα 4.2   Τα δυνατά αποτελέσματα επιλογής $k$ αντικειμένων από $n$ με επανάθεση είναι ίσα σε πλήθος με τις δυνατές διαμερίσεις του $k$ σε $n$ κομμάτια. Έχουμε δηλαδή

$${\left\langle{{n} \atop {k}}\right\rangle} = {n+k-1 \choose k}.$$

Άσκηση 4.4   Αν επιλέξουμε $k$ αντικείμενα από $n$ με επανάθεση και δεν αγνοήσουμε τη σειρά των επιλογών (π.χ., αν επιλέγουμε 3 αντικείμενα από τα Α, Β με επανάθεση, τα αποτελέσματα ΑΑΒ και ΑΒΑ θεωρούνται τώρα διαφορετικά), πόσες διαφορετικές επιλογές υπάρχουν;

Άσκηση 4.5   Αν έχετε ένα σωρό από άπειρες όμοιες μπάλες και $n$ αριθμημένα κουτιά χωρητικότητας $n$ μπαλών το καθένα με πόσους τρόπους μπορείτε να τοποθετήσετε κάποιες μπάλες στα κουτιά;

Ίδιο ερώτημα αν τα κουτιά δεν είναι αριθμημένα.

Άσκηση 4.6   Σε ένα ασανσέρ μπαίνουν 8 άτομα στο ισόγειο ενός κτηρίου. Ξεκινάει την πορεία του προς τα πάνω από το ισόγειο (όροφος 0) και σταματάει στον τελευταίο όροφο που είναι ο όροφος Νο 6.

Με πόσους διαφορετικούς τρόπους μπορεί να έχουν συμβεί οι αποβιβάσεις των 8 ατόμων αν

1. Οι 8 επιβάτες είναι πανομοιότυποι μεταξύ τους.
2. Υπάρχουν 5 άνδρες επιβάτες και 3 γυναίκες. Άτομα του ίδιου φύλου δεν ξεχωρίζουν μεταξύ τους.
3. Κάντε τις προηγούμενες περιπτώσεις υποθέτοντας ότι συμβαίνει τουλάχιστον μια αποβίβαση στον 6ο όροφο (αλλιώς δε θα είχε λόγο το ασανσέρ να ανέβει ως εκεί) ή, αντίθετα, χωρίς να υποθέσετε κάτι τέτοιο (υποθέστε δηλ. ότι το ασανσέρ πάντα πάει ως τον 6ο, ακόμη κι αν δεν έχει να αποβιβάσει κάποιον εκεί).

Άσκηση 4.7   Με πόσους τρόπους μπορούμε να επιλέξουμε τους ακεραίους $x_1, x_2, \ldots, x_k$ τ.ώ. να ισχύει $1 \le x_1 < x_2 < \cdots < x_k \le n$;

Άσκηση 4.8   Αποδείξτε ότι, για $k$ σταθερό, η συνάρτηση

$${\left\langle{{n} \atop {k}}\right\rangle} - {n \choose k}$$

είναι πολυώνυμο του $n$ και ότι, ανάλογα με το αν το $k$ είναι άρτιο ή περιττό, το πολυώνυμο αυτό περιέχει ή μόνο άρτιες δυνάμεις του $n$ ή μόνο περιττές. Βρείτε το άθροισμα των συντελεστών του πολυωνύμου αυτού.

Παράδειγμα 4.2   (Αλυσίδες DNA κατά Gamow) Μια αλυσίδα DNA είναι μια πεπερασμένη σειρά από χημικές βάσεις. Οι βάσεις αυτές είναι γνωστές με τα σύμβολα A, C, G και T. Ένα αμινοξύ είναι μια αλυσίδα DNA και είναι γνωστό ότι υπάρχουν ακριβώς 20 αμινοξέα. Αν υποθέσουμε ότι όλα τα αμινοξέα είναι αλυσίδες με το ίδιο μήκος, τότε εύκολα βλέπουμε ότι το μήκος αυτό δε μπορεί να είναι 1 ή 2. Πράγματι υπάρχουν ακριβώς 4 αλυσίδες μήκους 1 (οι A, C, G και T) και $4^2=16$ αλυσίδες μήκους 2 (αυτό γιατί μια τέτοια αλυσίδα ορίζεται από δύο επιλογές με 4 δυνατότητες για την κάθε μία). Από την άλλη μεριά οι αλυσίδες DNA μήκους 3 είναι το πλήθος $4^3=64$, είναι δηλ. περισσότερες από 20.

Το 1954 ο G. Gamow πρότεινε ότι δύο αλυσίδες DNA κωδικοποιούν το ίδιο αμινοξύ αν και μόνο αν περιέχουν τις ίδιες βάσεις ανεξαρτήτως σειράς. Οι αλυσίδες δηλ. ACC και CAC, αν και διαφορετικές, κωδικοποιούν το ίδιο αμινοξύ. Αν η υπόθεση του Gamow είναι σωστή πόσα διαφορετικά αμινοξέα κωδικοποιούνται με αλυσίδες DNA μήκους 3; Με λίγη σκέψη βλέπουμε ότι το πλήθος των διαφορετικών αμινοξέων είναι το ίδιο με το πλήθος των διαφορετικών συνδυασμών των τεσσάρων γραμμάτων A, C, G και T ανά τρία, με επανάθεση. Ο αριθμός αυτός είναι δηλ.

$${\left\langle{{4} \atop {3}}\right\rangle} = {4+3-1 \choose 3} = {6 \choose 3} = \frac{6\cdot 5\cdot 4}{3!} = 20,$$

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

Άσκηση 4.9   Με πόσους τρόπους μπορούμε να τοποθετήσουμε $n$ όμοιες μπάλες σε $k$ κουτιά που είναι αριθμημένα με τους αριθμούς 1 έως $k$;

Ίδιο ερώτημα όταν και οι μπάλες είναι αριθμημένες.

Παράδειγμα 4.3   (Η κατανομή Bose-Einstein στη στατιστική μηχανική)
Στη στατιστική μηχανική εξετάζουμε ένα σύστημα από $t$ σωμάτια κάθε ένα από τα οποία μπορεί να βρίσκεται σε $p$ διαφορετικές καταστάσεις, π.χ. σε $p$ διαφορετικά ενεργειακά επίπεδα. Μια κατάσταση του συστήματος είναι η περιγραφή της κατάστασης του κάθε σωματιδίου. Όταν τα σωμάτια είναι ίδια μεταξύ τους υποθέτουμε συνήθως ότι δεν έχει σημασία ποια από τα $t$ σωμάτια είναι στο κάθε ενεργειακό επίπεδο αλλά μόνο πόσα. Η υπόθεση ότι όλες αυτές οι καταστάσεις είναι εξίσου πιθανές λέγεται κατανομή Bose-Einstein.

Στο μοντέλο Bose-Einstein πόσες διαφορετικές καταστάσεις του συστήματος υπάρχουν; Αν θέσουμε $x_i$, $i=1,\ldots,p$, να είναι το πλήθος των σωματίων στο ενεργειακό επίπεδο $i$, τότε πρέπει απλά να διαλέξουμε τους μη αρνητικούς ακεραίους $x_i$ ώστε να έχουν άθροισμα $t$. Δηλαδή το πλήθος καταστάσεων του συστήματος είναι ίσο με το πλήθος των διαμερίσεων του $t$ σε $p$ κομμάτια, δηλ.

$${t + p -1 \choose t}.$$

Άσκηση 4.10   Στην κατανομή Fermi-Dirac υποθέτουμε ότι τα $t$ σωμάτια είναι όλα όμοια και ότι δε μπορούν δύο σωμάτια να βρίσκονται στο ίδιο ενεργειακό επίπεδο (υπάρχουν $p$ ενεργειακά επίπεδα). Αν $t \le p$ πόσες διαφορετικές καταστάσεις του συστήματος σωματίων υπάρχουν; (Δείτε το Παράδειγμα 4.3 και την Άσκηση 4.9.)