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

Συντονιστές: Demetres, socrates, silouan

Λάμπρος Κατσάπας
Δημοσιεύσεις: 716
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

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

#1

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Κυρ Οκτ 13, 2019 12:25 am

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

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

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

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

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

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

Σημείωση 2: Για παράδειγμα, αν n=3, έχουμε τις παρακάτω δυνατές διατάξεις
Συνημμένα
BALLS.JPG
BALLS.JPG (38.05 KiB) Προβλήθηκε 646 φορές



Λέξεις Κλειδιά:
Λάμπρος Κατσάπας
Δημοσιεύσεις: 716
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

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

#2

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Τρί Οκτ 15, 2019 3:20 pm

Επαναφορά.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8493
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Οκτ 16, 2019 10:35 am

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

Στη διάταξη, κοιτάζω τη δεύτερη σειρά από κάτω και πόσες σφαίρες έχει από τα αριστερά μέχρι να βρω το πρώτο κενό. Έστω ότι υπάρχουν k σφαίρες. Φέρνω μια κάθετη γραμμή η οποία χωρίζει τις n+1 σφαίρες της τελευταίας γραμμής σε k+1 σφαίρες αριστερά και n-k σφαίρες δεξιά. Κάθε άλλη σφαίρα θα βρίσκεται είτε στα αριστερά της γραμμής είτε στα δεξιά.

Πάνω από τις k+1 σφαίρες αριστερά υπάρχουν k σφαίρες και η διάταξη μπορεί να συμπληρωθεί με 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}


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Seniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης