Συνδυασμοί με επαναλήψεις

Οι συνδυασμοί με επαναλήψεις μοιάζουν με τους κλασικούς συνδυασμούς, με τη διαφορά ότι επιτρέπουμε στα στοιχεία του βασικού συνόλου M να επαναλαμβάνονται.

Ορισμός και τύπος

Ας ξεκινήσουμε με ένα ωραίο παράδειγμα: μπαίνεις σε ένα κατάστημα και θέλεις να αγοράσεις δώδεκα μπουκάλια μπίρας για μια εκδρομή. Στο ράφι έχουν συνολικά τέσσερις διαφορετικές μπίρες. Τώρα έχεις αρκετές δυνατότητες: μπορείς να αγοράσεις, για παράδειγμα, 5 Μύθος, 2 Άλφα, 1 Φιξ και 4 Νήσος ή να αγοράσεις από κάθε παραγωγό ακριβώς τρία μπουκάλια. Πόσοι διαφορετικοί τρόποι υπάρχουν να αγοράσεις τα μπουκάλια, ώστε να έχεις ακριβώς δώδεκα;

Έχουμε λοιπόν το βασικό σύνολο M = {Μύθος, Άλφα, Φιξ, Νήσος} και ρωτάμε πόσες κ-άδες, με κ = 12, περιέχουν στοιχεία του συνόλου M και στις οποίες δεν έχει σημασία η σειρά.

Η εξαγωγή του τύπου είναι αρκετά πιο σύνθετη απ' ό,τι στις υπόλοιπες συνδυαστικές ασκήσεις. Αρχικά φανταζόμαστε την αγορά μας ως μια ακολουθία από μηδενικά και μονάδες, έτσι ώστε το πλήθος των μονάδων να αντιστοιχεί στο πλήθος των μπουκαλιών του συγκεκριμένου παραγωγού και το μηδενικό να χωρίζει τους παραγωγούς μεταξύ τους. Έτσι η ακολουθία 111011101111101 λέει ότι αγοράσαμε τρία Μύθος (οι τρεις πρώτες μονάδες), μετά τρία Άλφα (το 0 είναι διαχωριστικό, ακολουθούν άλλες τρεις μονάδες), μετά πέντε Φιξ (0 διαχωριστικό και μετά πέντε μονάδες) και τέλος ένα Νήσος. Όλη η ιδέα φαίνεται στην παρακάτω εικόνα:

$$\underset{\text{Μυθ}}{\underbrace{111}}0\underset{\text{Αλφ}}{\underbrace{111}}0\underset{\text{Φιξ}}{\underbrace{11111}}0\underset{\text{Νησ}}{\underbrace{1}}$$

Αν θέλαμε να αγοράσουμε 6 Μύθος, 4 Άλφα, 2 Νήσος και κανένα Φιξ, η ακολουθία θα έμοιαζε έτσι:

$$\underset{\text{Μυθ}}{\underbrace{111111}}0\underset{\text{Αλφ}}{\underbrace{1111}}00\underset{\text{Νησ}}{\underbrace{11}}$$

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

Αρκεί να υπολογίσουμε τη θέση των μηδενικών – μόλις μοιράσουμε 3 μηδενικά ανάμεσα στις 12 μονάδες, έχουμε έναν έγκυρο συνδυασμό μπιρών. Με άλλα λόγια: έχουμε συνολικά 15 θέσεις και πρέπει να καταλάβουμε τις 3 από αυτές με μηδενικό. Τις υπόλοιπες θέσεις τις γεμίζουμε αυτόματα με μονάδες.

Αυτό είναι πια μια απλή άσκηση στους συνδυασμούς χωρίς επαναλήψεις. Αριθμούμε τις 15 θέσεις με τους αριθμούς {1, …, 15} και από αυτό το σύνολο επιλέγουμε κάθε φορά τριάδες αριθμών, οπότε παίρνουμε τρεις δείκτες, όπου θα τοποθετήσουμε το μηδενικό. Π.χ. για τον συνδυασμό {2, 4, 7} θα παίρναμε την ακολουθία 101011011111111. Στη 2η, στην 4η και στην 7η θέση υπάρχει μηδενικό, οι υπόλοιπες είναι μονάδες. Υπάρχουν λοιπόν συνολικά

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

διαφορετικοί τρόποι να μοιράσουμε τα μηδενικά στις 15 θέσεις και άρα και 455 διαφορετικές δυνατότητες να αγοράσουμε 12 μπίρες, όταν έχουμε τέσσερα διαφορετικά είδη μπίρας.

Τον προηγούμενο συλλογισμό μπορούμε να τον γενικεύσουμε. Αν έχουμε ένα σύνολο στοιχείων M με ν στοιχεία και επιλέγουμε από αυτό κ-άδες, όπου τα στοιχεία μπορούν να επαναλαμβάνονται, τότε σχηματίζουμε μια ακολουθία από μηδενικά και μονάδες μήκους ν + κ − 1 (κ μονάδες και ν − 1 μηδενικά) και βρίσκουμε με πόσους τρόπους μπορούμε να τοποθετήσουμε τα ν − 1 μηδενικά, άρα το πλήθος των συνδυασμών με επαναλήψεις, που το συμβολίζουμε ${{\mathrm{\Sigma }}^{\prime }}_{\nu }^{\kappa }$, είναι ίσο με

$${{\mathrm{\Sigma }}^{\prime }}_{\nu }^{\kappa }=(\genfrac{}{}{0ex}{}{\nu +\kappa -1}{\nu -1})=(\genfrac{}{}{0ex}{}{\nu +\kappa -1}{\kappa }).$$

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

Λυμένα παραδείγματα

1. Με πόσους τρόπους μπορούν να μοιραστούν 20 δωρεάν εισιτήρια για την πρεμιέρα μιας παράστασης σε 10 συνταξιούχες; Αυτό είναι παράδειγμα συνδυασμών με επαναλήψεις, επειδή μία συνταξιούχος μπορεί να πάρει περισσότερα, δυνητικά ακόμη και όλα, τα δωρεάν εισιτήρια. Πρέπει απλώς να καταλάβουμε σωστά τι είναι το ν και τι το κ. Στην πραγματικότητα επιλέγουμε συνδυασμούς 20 στοιχείων από 10 συνταξιούχες, με άλλα λόγια σχηματίζουμε μια ακολουθία από μηδενικά και μονάδες με μήκος 29, που περιέχει 20 μονάδες και 9 μηδενικά. Άρα ν = 10, κ = 20. Παίρνουμε το αποτέλεσμα:

$${{\mathrm{\Sigma }}^{\prime }}_{10}^{20}=(\genfrac{}{}{0ex}{}{10+20-1}{20})=10.015.005.$$