Πλήθος διατάξεων σφαιρών

Λάμπρος Κατσάπας · #1

Έχουμε στη διάθεσή μας καποιόν αριθμό από όμοιες μπάλες και θέλουμε να τις διατάξουμε σε σειρές.

Σε κάθε σειρά οι μπάλες πρέπει να εφάπτονται και επιπλέον κάθε μπάλα,

όχι της κάτω σειράς, να εφάπτεται με δύο μπάλες της ακριβώς από κάτω σειράς.

Να βρεθεί το πλήθος των δυνατών διατάξεων αν στην κάτω σειρά έχουμε

μπάλες.

Σημείωση 1: Θεωρείστε ότι έχουμε στη διάθεση μας αρκετές (συγκεκριμένα $\dfrac{n(n+1)}{2}$ )

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

Σημείωση 2: Για παράδειγμα, αν n=3

, έχουμε τις παρακάτω δυνατές διατάξεις

Λάμπρος Κατσάπας · #2

Επαναφορά.

#3

Ας γράψουμε C_n

για το ζητούμενο πλήθος. Έχουμε $C_1 = 1, C_2=2,C_3=5,\ldots$ . Ορίζω επίσης C_0 = 1

.

Στη διάταξη, κοιτάζω τη δεύτερη σειρά από κάτω και πόσες σφαίρες έχει από τα αριστερά μέχρι να βρω το πρώτο κενό. Έστω ότι υπάρχουν

σφαίρες. Φέρνω μια κάθετη γραμμή η οποία χωρίζει τις n+1

σφαίρες της τελευταίας γραμμής σε k+1

σφαίρες αριστερά και n-k

σφαίρες δεξιά. Κάθε άλλη σφαίρα θα βρίσκεται είτε στα αριστερά της γραμμής είτε στα δεξιά.

Πάνω από τις k+1

σφαίρες αριστερά υπάρχουν

σφαίρες και η διάταξη μπορεί να συμπληρωθεί με C_k

τρόπους. Στη δεξιά πλευρά η διάταξη μπορεί να συμπληρωθεί με $C_{n-k}$ τρόπους.

Έχουμε λοιπόν τον αναδρομικό τύπο $\displaystyle C_{n+1} = \sum_{k=0}^{n} C_kC_{n-k}$ ο οποίος είναι ο αναδρομικός τύπος της ακολουθίας Catalan με τις ίδιες αρχικές συνθήκες.

Άρα $\displaystyle C_n = \frac{1}{n+1}\binom{2n}{n}$

Πλήθος διατάξεων σφαιρών

Πλήθος διατάξεων σφαιρών

Re: Πλήθος διατάξεων σφαιρών

Re: Πλήθος διατάξεων σφαιρών

Μέλη σε σύνδεση