ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

#1

Γεια σας !
Τυχαία και με αφορμή ένα απλό πρόβλημα συνδυαστικής σε εισαγωγικές στην Ινδία, διαπίστωσα το εξής :

Ενώ έχω συναντήσει στα μοντέλα καταλήψεων την εύρεση των τρόπων κατανομής όμοιων σφαιριδίων σε διακεκριμένα κελιά, δεν έχω δει όμως τι γίνεται αν τα κελιά είναι όμοια, αν δεν ενδιαφέρει δηλαδή η θέση τους.

Έτσι, πχ, στην τοποθέτηση 9 ίδιων μπαλών σε

ίδια κουτιά , οι κατανομές (9,0,0)

και

είναι ίδιες.
Στο παράδειγμα αυτό, με καταγραφή βρίσκουμε έχουμε

τρόπους.

Θα μπορούσαμε άραγε να δώσουμε στο παράδειγμα πιο ...συνδυαστική λύση, πχ υποθέτοντας ότι τα κουτιά είναι διαφορετικά και μετά να αφαιρέσουμε τις διπλο ή τριπλο-μετρημένες περιπτώσεις ;

Μπορεί μια τέτοια μέθοδος να γενικευτεί κάπως ;

Έχει μήηπως κάποιος συναντήσει γενικότερους τρόπους απαρίθμησης αυτών των κατανομών , έστω και σε μερικές περιπτώσεις ;

Σας ευχαριστώ-Καλό φθινόπωρο και καλή Ακαδημαϊκή ή Σχολική χρονιά !

giannispapav · #2

Στην περίπτωση που απαιτήσουμε κάθε κελί να έχει τουλάχιστον μία μπάλα, τότε, αν δεν κάνω λάθος (πολύ πιθανό), οι ζητούμενες κατανομές είναι σε πλήθος όσος και ο αριθμός p(n,k)

στο https://reader.elsevier.com/reader/sd/p ... 0928182135 αλλά δεν ξέρω αν αυτό βοηθά ουσιαστικά για τη γενική περίπτωση.

#3

giannispapav έγραψε: Τετ Σεπ 28, 2022 9:37 pm Στην περίπτωση που απαιτήσουμε κάθε κελί να έχει τουλάχιστον μία μπάλα, τότε, αν δεν κάνω λάθος (πολύ πιθανό), οι ζητούμενες κατανομές είναι σε πλήθος όσος και ο αριθμός στο https://reader.elsevier.com/reader/sd/p ... 0928182135 αλλά δεν ξέρω αν αυτό βοηθά ουσιαστικά για τη γενική περίπτωση.

Καλημέρα !
Μπορεί να βοηθήσει ίσως γιατί όπως μου είπε ο Σταύρος Παπαδόπουλος μπορούμε να θεωρήσουμε ότι έχουμε n+k

μπάλες, να βάλουμε τις

, από μία στα

$ κελιά και τις άλλες τελείως τυχαία. Πρέπει μόνο να δούμε πόσες περιπτώσεις θα αφαιρέσουμε.
Έχουμε δουλειά !

Σε ευχαριστώ πολύ!

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #4

Στο βιβλίο Συνδιαστική τόμος 2 του Χ.Α.Χαραλαμπίδη το πρώτο κεφάλαιο ασχολείται με ακριβώς αυτό
το πρόβλημα.
Είναι τετριμμένο ότι
Ο αριθμός των τρόπων να βάλουμε

όμοιες μπάλες σε

όμοια κελιά είναι ίσος
με τον αριθμό των τρόπων να βάλουμε n+k

όμοιες μπάλες σε

όμοια κελιά με
την προυπόθεση ότι σε κάθε κελί θα υπάρχει τουλάχιστον μία μπάλα.

(x_1,x_2,,...,x_k)<-->(x_1+1,x_2+1,,...,x_k+1)

Karolina Papachrys · #5

Το πλήθος των διαμερίσεων ενός ακέραιου n σε το πολύ 3 μέρη είναι ίσο με τον πλησιέστερο ακέραιο στον:
$(n+3){^{2}}/12$
Για παράδειγμα, για n=9 έχουμε 12 και για n=12 έχουμε 19 τέτοιες διαμερίσεις.

Απόδειξη στο βιβλίο του Hardy G.H.: Some famous problems of the theory of numbers, p.8-10.

#6

Karolina Papachrys έγραψε: Πέμ Σεπ 29, 2022 5:37 pm Το πλήθος των διαμερίσεων ενός ακέραιου n σε το πολύ 3 μέρη είναι ίσο με τον πλησιέστερο ακέραιο στον:
$(n+3){^{2}}/12$
Για παράδειγμα, για n=9 έχουμε 12 και για n=12 έχουμε 19 τέτοιες διαμερίσεις.

Απόδειξη στο βιβλίο του Hardy G.H.: Some famous problems of the theory of numbers, p.8-10.

Καρολίνα, αυτή είναι εξαιρετική ..είδηση.

Θα ψάξω και αυτό το βιβλίο και του Χαραλαμπίδη που ανέφερε παραπάνω ο Σταύρος.

Σε ευχαριστώ πολύ !

Πέρα τώρα από αυτά, ένας συνάδελφος , o Κώστας Καπούλας , που του αρέσουν αυτά (από τους λίγους που διάβαζε μανιωδώς

Θεόφιλο Κάκκουλο στην Αθήνα το 1975), ύστερα από κάποιες κοινές αναζητήσεις, απέδειξε χθες ότι με 3 μη διακεκριμένα κουτιά

(κελιά) και

μπάλες έχουμε :

(α) $\frac {C(n+2,2)+3k+3}{6}$ τρόπους, αν ο

δεν είναι πολλαπλάσιο του

και

τέτοιος ώστε n=2k

ή

(β) $\frac {C(n+2,2)+3k+5}{6}$ τρόπους, αν ο

είναι πολλαπλάσιο του

και

τέτοιος ώστε n=2k

ή

Αμέσως θα καταλάβατε ότι οι συνδυασμοί C(n+2,2)

στους αριθμητές είναι οι επαναληπτικοί συνδυασμοί των

ανά

.

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

κουτιά το ζήτημα ήταν σχετικά απλό.

Καλή δύναμη και καλή συνέχει, ό,τι και να κάνετε !!!

#7

Με

συμβολίζουμε το πλήθος των τρόπων που μπορούμε να γράψουμε τον

σαν άθροισμα θετικών ακεραίων χωρίς να παίζει ρόλο η σειρά. Π.χ. p(5) = 7

επειδή έχουμε 5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1

.

Με

συμβολίζουμε το πλήθος των τρόπων που μπορούμε να γράψουμε τον

σαν άθροισμα

θετικών ακεραίων χωρίς να παίζει ρόλο η σειρά. Π.χ. p_2(5) = 2

επειδή έχουμε 5 = 4+1 = 3+2

.

Στην περίπτωσή μας ουσιαστικά θέλουμε το p_1(9) + p_2(9) + p_3(9)

και ομοίως για παρόμοια παραδείγματα. Η δυσκολία είναι ότι δεν υπάρχει έτοιμος τύπος όπως σε άλλες συνδυαστικές ασκήσεις.

Ένας τρόπος να το υπολογίσουμε είναι μέσω του αναδρομικού τύπου

$p_(n) = p_k(n-k) + p_{k-1}(n-1)$ με αρχικές συνθήκες p_0(0) = 1

και

για

.

Δεν είναι δύσκολο να αποδειχθεί το πιο πάνω: Αν χρησιμοποοιήσουμε τουλάχιστον ένα άσσο υπάρχουν $p_{k-1}(n-1)$ τρόποι. Αν δεν χρησιμοποιήσουμε κανέναν άσσο τότε υπάρχουν p_k(n-k)

τρόποι αφού η γραφή $n = x_1 + \cdots + x_k$ με $x_i \geqslant 2$ αντιστοιχεί στη γραφή $n-k = (x_1-1) + \cdots + (x_k-1)$ .

Για μικρές τιμές του

μπορούμε να βρούμε ακριβώς τι γίνεται. Προφανώς p_1(n) = 1

για κάθε $n \geqslant 1$ και $p_2(n) =\left\lfloor n/2\right\rfloor$ για κάθε $n \geqslant 1$ . (Δεν χρειάζεται καν ο αναδρομικός τύπος εδώ.)

Άρα p_1(9) = 1

και

. Για το

έχουμε

$\displaystyle p_3(9) = p_3(6) + p_2(8) = p_3(6) + 4 = p_3(3) + p_2(5) + 4 = 1 + 2 + 4 = 7$

Η τελική απάντηση για το συγκεκριμένο πρόβλημα είναι λοιπόν 1+4+7 = 12

.

Ασυμπτωτικά (όταν $n \to \infty$ ) μπορούν να δειχθούν τα εξής: $\displaystyle p_k(n) \sim \frac{n^{k-1}}{k!(k-1)!}$ και $\displaystyle p(n) \sim \frac{1}{4n\sqrt{3}}\exp\left( \pi\sqrt{\frac{2n}{3}}\right)$

#8

Δημήτρη, καλό μήνα !

Σε ευχαριστώ πολύ. Ήταν πολύ χρήσιμα και κατανοητά όλα αυτά που έγραψες και με βάζεις στον πειρασμό να τα μελετήσω ξανά, την αναγωγή βασικά !

Έχω και τον Χαραλαμπίδη (ΣΥΝΔΥΑΣΤΙΚΗ ΤΟΜΟΣ 2) που υπέδειξε ο Σταύρος, οπότε θα πάρω μια καλή γεύση, έτσι από περιέργεια κυρίως !

ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

Re: ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

Re: ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

Re: ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

Re: ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

Re: ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

Re: ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

Re: ΚΑΤΑΝΟΜΗ ΟΜΟΙΩΝ ΣΦΑΙΡΙΔΙΩΝ ΣΕ ΟΜΟΙΑ ΚΕΛΙΑ

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