Διατάξεις με επαναλήψεις

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

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

Θα ξεκινήσουμε με ένα κλασικό παράδειγμα: πόσες διαφορετικές λέξεις μπορούμε να φτιάξουμε από τα γράμματα του αγγλικού αλφαβήτου (abc … xyz, είναι 26), αν η λέξη πρέπει να έχει μήκος 6; Έξι γράμματα δεν είναι πολλά, κι όμως οι λέξεις θα είναι αρκετές. Δεν μας ενδιαφέρει το νόημα των λέξεων, οπότε και το «weqrww» το θεωρούμε έγκυρη λέξη μήκους έξι.

Για τον υπολογισμό χρειαζόμαστε μόνο την πολλαπλασιαστική αρχή. Έχουμε συνολικά 26 διαφορετικά γράμματα που μπορούμε να χρησιμοποιήσουμε. Στην πρώτη θέση μπορούμε λοιπόν να βάλουμε ένα από τα 26 γράμματα. Και στη δεύτερη θέση μπορούμε επίσης να βάλουμε ένα από τα 26 γράμματα, γιατί δεν βάλαμε όρο ότι τα γράμματα δεν επιτρέπεται να επαναλαμβάνονται. Έτσι φτάνουμε στο ότι σε κάθε θέση επιλέγουμε από 26 γράμματα και ο συνολικός αριθμός των διατάξεων είναι, σύμφωνα με την πολλαπλασιαστική αρχή, 26⁶ = 308.915.776. Είναι αρκετά πολλές, αν σκεφτεί κανείς ότι χρησιμοποιήσαμε μόνο 26 γράμματα.

Λέμε ότι μια διάταξη με επαναλήψεις των ν στοιχείων του συνόλου M ανά κ είναι κάθε διατεταγμένη κ-άδα της οποίας τα στοιχεία ανήκουν στο σύνολο M και κάθε στοιχείο μπορεί να εμφανίζεται στην κ-άδα έως και κ φορές. Αν έχουμε λοιπόν το σύνολο M = {1, 2, 3}, τότε όλες οι παρακάτω είναι έγκυρες διατάξεις με επαναλήψεις ανά 4: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Το πλήθος τέτοιων διατάξεων με επαναλήψεις, που το συμβολίζουμε ${{\mathrm{\Delta }}^{\prime }}_{\nu }^{\kappa }$, είναι τότε ίσο με

$${{\mathrm{\Delta }}^{\prime }}_{\nu }^{\kappa }={\nu }^{\kappa }.$$

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

1. Πόσους εξαψήφιους αριθμούς μπορούμε να σχηματίσουμε από τα ψηφία {2, 4, 6, 8}, αν τα ψηφία μπορούν να επαναλαμβάνονται; Απλώς αντικαθιστούμε στον τύπο, το σύνολο έχει μέγεθος 4 και επιλέγουμε εξάδες:

   $${{\mathrm{\Delta }}^{\prime }}_4^6=4^6=4096.$$

2. Στους υπολογιστές χρησιμοποιείται συνήθως το δυαδικό σύστημα αριθμών, δηλαδή το σύστημα που χρησιμοποιεί μόνο τα ψηφία 0 και 1. Εισάγονται εκεί νέες μονάδες, π.χ. ένα bit αντιπροσωπεύει ένα είδος κελιού, στο οποίο αποθηκεύεται ακριβώς ή το μηδέν ή το ένα. Μεγαλύτερο είναι το byte, που περιέχει 8 bit. Άρα το 1 είναι ένα bit, ενώ το 01110001 είναι ένα byte. Με πόσους διαφορετικούς τρόπους μπορούμε να γεμίσουμε ένα byte με 8 bit;

   Επιλέγουμε από το σύνολο {0, 1}, δηλαδή από δύο στοιχεία. Επιλέγουμε κ-άδα μεγέθους κ = 8, άρα το πλήθος όλων των δυνατοτήτων είναι ίσο με

   $${{\mathrm{\Delta }}^{\prime }}_2^8=2^8=256.$$

3. Από το προηγούμενο παράδειγμα ξέρουμε ότι ένα byte μπορεί να ξεχωρίσει έως και 256 διαφορετικές τιμές. Με πόσους τρόπους μπορούμε να γεμίσουμε 4 byte;

   Τέσσερα byte περιέχουν 4 · 8 = 32 bit, και πάλι επιλέγουμε από σύνολο μεγέθους 2. Άρα το αποτέλεσμα είναι:

   $${{\mathrm{\Delta }}^{\prime }}_2^{32}=2^{32}=4.294.967.296.$$

   Βλέπουμε ότι μόλις τέσσερα byte μπορούν να ξεχωρίσουν πάνω από τέσσερα δισεκατομμύρια τιμές. Για να πάρεις μια ιδέα: οι σημερινοί υπολογιστές έχουν δίσκους μεγέθους εκατοντάδων gigabyte ή και terabyte. Ένα terabyte περιέχει 1.000.000.000.000 byte και άρα 8.000.000.000.000 bit. Σε έναν δίσκο ενός terabyte μπορούμε λοιπόν να αποθηκεύσουμε έως και 2^{8.000.000.000.000} διαφορετικές τιμές.

   Σημείωση: σήμερα επικρατεί μια μικρή σύγχυση στην έννοια του kilobyte (megabyte κ.ο.κ.). Για τεχνολογικούς λόγους ίσχυε ότι ένα kilobyte δεν περιέχει 1000 byte, όπως συνηθίζεται στις άλλες μονάδες (ένα χιλιόγραμμο ισούται με χίλια γραμμάρια), αλλά ένα kilobyte ήταν ίσο με 2¹⁰ byte, δηλαδή 1024 byte. Ένα megabyte ήταν τότε 2²⁰ byte ή επίσης 2¹⁰ kilobyte.

   Σήμερα ξεχωρίζουμε λοιπόν δύο είδη γραφής: 1 kB (kilobyte) είναι 1000 byte και 1 KiB (kibibyte) είναι 2¹⁰ = 1024 byte.

4. Ένα ακόμα παράδειγμα βρίσκεται σε ξεχωριστό άρθρο που ασχολείται με την ασφάλεια του κωδικού πρόσβασης.