Μεταθέσεις

Εισαγωγή στις Μεταθέσεις

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

Ορισμός Μετάθεσης

Μετάθεση $n$ διαφορετικών αντικειμένων είναι κάθε διάταξη όλων των αντικειμένων σε μια σειρά. Ο αριθμός όλων των μεταθέσεων $n$ αντικειμένων είναι:

$$P_n = n! = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot 1$$

Παραγοντικό (Factorial)

Το παραγοντικό ενός μη αρνητικού ακεραίου $n$ συμβολίζεται $n!$ και ορίζεται:

$$n! = \begin{cases} 1 & \text{αν } n = 0 \\ n \cdot (n-1)! & \text{αν } n \geq 1 \end{cases}$$

Παραδείγματα:

• $0! = 1$ (εξ ορισμού)
• $1! = 1$
• $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$
• $10! = 3628800$

Χρήσιμες ιδιότητες:

• $n! = n \cdot (n-1)!$
• $\frac{n!}{(n-1)!} = n$
• $\frac{n!}{(n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)$

Διατάξεις χωρίς Επανάληψη

Ο αριθμός των τρόπων για να διατάξουμε $k$ αντικείμενα από σύνολο $n$ διαφορετικών αντικειμένων (χωρίς επανάληψη) είναι:

$$P(n,k) = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)$$

Όταν $k = n$, έχουμε τη μετάθεση όλων των στοιχείων:

$$P(n,n) = n!$$

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

Αν επιτρέπεται η επανάληψη αντικειμένων, ο αριθμός των διατάξεων $k$ θέσεων από $n$ αντικείμενα είναι:

$$n^k$$

Μεταθέσεις με Επαναλήψεις

Αν έχουμε $n$ αντικείμενα που περιέχουν $k$ ομάδες όμοιων στοιχείων με $n_1, n_2, ..., n_k$ στοιχεία αντίστοιχα (όπου $n_1 + n_2 + ... + n_k = n$), τότε ο αριθμός των διαφορετικών μεταθέσεων είναι:

$$\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}$$

Παράδειγμα: Αναγραμματισμοί

Πόσοι αναγραμματισμοί υπάρχουν για τη λέξη "ΜΑΘΗΜΑ";

• Σύνολο γραμμάτων: 6
• Επαναλήψεις: Μ εμφανίζεται 2 φορές, Α εμφανίζεται 2 φορές

$$\frac{6!}{2! \cdot 2!} = \frac{720}{4} = 180 \text{ αναγραμματισμοί}$$

Κυκλικές Μεταθέσεις

Όταν τα αντικείμενα τοποθετούνται σε κύκλο (π.χ. γύρω από ένα τραπέζι), ο αριθμός των διαφορετικών διατάξεων είναι:

$$(n-1)!$$

Αυτό συμβαίνει διότι σε κυκλική διάταξη δεν υπάρχει "πρώτη" θέση - οι περιστροφές θεωρούνται ίδιες.

Παράδειγμα: Κυκλική Διάταξη

Με πόσους τρόπους μπορούν να καθίσουν 6 άτομα γύρω από ένα στρογγυλό τραπέζι;

$$(6-1)! = 5! = 120 \text{ τρόποι}$$

Μεταθέσεις με Περιορισμούς

Συχνά τα προβλήματα μεταθέσεων έχουν περιορισμούς που πρέπει να ληφθούν υπόψη.

Περιορισμός: Ορισμένα στοιχεία μαζί

Αν $k$ στοιχεία πρέπει να είναι μαζί, τα θεωρούμε ως μία ομάδα:

• Μεταθέσεις των ομάδων: $(n-k+1)!$
• Μεταθέσεις εντός της ομάδας: $k!$
• Σύνολο: $(n-k+1)! \cdot k!$

Περιορισμός: Ορισμένα στοιχεία ΟΧΙ μαζί

Υπολογίζουμε: (Όλες οι μεταθέσεις) - (Μεταθέσεις με τα στοιχεία μαζί)

Παράδειγμα με Περιορισμό

5 άτομα (Α, Β, Γ, Δ, Ε) κάθονται σε σειρά. Με πόσους τρόπους αν τα Α και Β πρέπει να κάθονται μαζί;

• Θεωρούμε τα Α, Β ως μία ομάδα
• Μεταθέσεις 4 «ομάδων»: $4! = 24$
• Μεταθέσεις Α, Β μέσα στην ομάδα: $2! = 2$
• Σύνολο: $24 \times 2 = 48$ τρόποι