ΚΥΚΛΙΚΕΣ ΜΕΤΑΘΕΣΕΙΣ

Α.Μ. 3857

Κυκλικές μεταθέσεις ω πραγμάτων α₁, α₂, α₃ …α_ν είναι οι διάφοροι τρόποι κατά τους οποίους μπορούμε να τοποθετήσουμε τα ν αυτά πράγματα σε μία περιφέρεια. Σ’ αυτή την περίπτωση σαν πρώτο στοιχείο πάνω στην περιφέρεια μπορούμε να λάβουμε οποιοδήποτε στοιχείο. Πχ το α₁, οπότε τα υπόλοιπα ν-1 πράγματα μπορούν να τοποθετηθούν πάνω στην περιφέρεια κατά (ν-1)! Διαφορετικούς τρόπους. Ώστε οι κυκλικές μεταθέσεις των ν πραγμάτων είναι (ν-1)!

Ας θεωρήσουμε ν διακεκριμένα στοιχεία τα οποία φέρουν τους αριθμούς 1,2,..,ν. Η παράθεση των αριθμών αυτών από το μικρότερο προς το μεγαλύτερο 1 2 3 … ν (1.1)

Αποτελεί τη φυσική διάταξη τούτων. Ας θεωρήσουμε και μια άλλη διάταξη αυτών, την α₁ α₂ α₃ … α_ν (1.2)

Η αντικατάσταση της διατάξεως (1.1) από την διάταξη (1.2) καλείται μετάθεση των ν θεωρηθέντων στοιχείων. Τη μετάθεση αυτή την παριστάνουμε με τη μορφή τελεστού με το σύμβολο

(1.3)

που ορίζει το νόμο της αντικαταστάσεως της (1.1) από την (1.2).

Ορίζει δηλαδή την αντικατάσταση του στοιχείου κ από το στοιχείο α_κ όπου κ=1,2,3,…,ν.

Από τον ορισμό αυτό προκύπτει ότι οι στήλες στην (1.3) μπορούν να αντιμετατίθενται.

Με αυτό υπ’ όψη η μετάθεση

(1.4)

καλείται κύκλος ή κυκλική μετάθεση. Την (1.4) παριστάνουμε με απλούστερο συμβολισμό , γράφοντας μέσα στις παρενθέσεις τον τρόπο της διαδοχής των μετατιθέντων στοιχείων : (α_j1, a_j2, ….,a_jν ).

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

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

Κλάσεις κυκλικών μεταθέσεων

Μία μετάθεση ν στοιχείων που αποτελείται από κ₁ μοναδιαίους κύκλους, κ₂ κύκλους δύο στοιχείων, κ.ο.κ, κ_ν κύκλους ν στοιχείων λέμε ότι είναι της κλάσεως (κ₁,κ₂,…,κ_ν). Αν C (κ₁,κ₂,…,κ_ν) είναι ο αριθμός των μεταθέσεων ν στοιχείων της κλάσης (κ₁,κ₂,…,κ_ν) έτσι ώστε

κ₁ + 2 κ₂ + … + ν κ_ν = ν

τότε

C (κ₁, κ₂, …, κ_ν) = (2.1)

Η σχέση (2.1) προκύπτει ως εξής : Ας θεωρήσουμε μία από τις μεταθέσεις της κλάσεως (κ₁,κ₂,…,κ_ν) και ας μεταθέσουμε τα ν στοιχεία αυτής κατά τους ν! δυνατούς τρόπους. Οι μεταθέσεις που προκύπτουν με αυτό τον τρόπο δεν είναι όλες διαφορετικές για δύο λόγους:1) όλοι οι κύκλοι που περιέχουν τα ίδια στοιχεία με την ίδια κυκλική διάταξη είναι οι ίδιοι και 2) η σχετική θέση των κύκλων δεν ενδιαφέρει. Σε ένα κύκλο με r στοιχεία όπως έχουμε παρατηρήσει, υπάρχουν r στοιχεία που μπορούν να καταλάβουν την πρώτη θέση και επομένως έχουμε r επαναλήψεις για τον πρώτο λόγο. Ο συνολικός αριθμός τέτοιων επαναλήψεων είναι

1^κ1 2^κ2 … ν^κν.

Για τον δεύτερο λόγο και επειδή κ_r κύκλοι με r στοιχεία μπορούν να μετατεθούν κατά κ_r! τρόπους, ο συνολικός αριθμός των επαναλήψεων είναι: κ₁! Κ₂!...κ_ν!.

Προκύπτει έτσι η σχέση (2.1)

Η γεννήτρια συνάρτηση των αριθμών είναι λόγω της (2.1) η

(2.2)

όπου η άθροιση λαμβάνεται για όλες τις ακέραιες μη αρνητικές τιμές των κ₁,κ₂,…,κ_ν με κ₁ + 2 κ₂ + … + ν κ_ν = ν

Η C_ν(t₁,t₂,…,t_ν) καλείται κυκλική δείκτρια της συμμετρικής ομάδας μεταθέσεων.

Συγκρίνοντας την σχέση(2.2) με την σχέση του εκθετικού πολυωνύμου

συμπεραίνουμε ότι

(2.3)

Από την εκθετική γεννήτρια των πολυωνύμων Ε_ν προκύπτει η εκθετική γεννήτρια των C_ν

(2.4)

ΜΕΤΑΘΕΣΕΙΣ ΜΕ ΚΑΘΟΡΙΣΜΕΝΟ ΑΡΙΘΜΟ ΚΥΚΛΩΝ

Πρόβλημα

Πόσες μεταθέσεις ν στοιχείων υπάρχουν με κ κύκλους ανεξάρτητα από το μήκος τους.

Λύση

Από την παραπάνω ανάπτυξη προκύπτει ότι η γεννήτρια των ζητούμενων αριθμών είναι η C_ν (t, t,…, t) ≡ c_ν (t) (3.1) που προκύπτει από την (2.2) αν θέσουμε t_i=t,i =1,2,…,ν .

Από τη σχέση (2.4) με t_i=t λαμβάνουμε :

και

c₀ (t) =1, c_ν (t) = (t) _ν, ν > 0 (3.2)

Η (3.2) είναι η γεννήτρια των απροσήμων αριθμών Stirling του πρώτου είδους c(ν,k)= (-1)^ν-k s(ν,k) δηλαδή c_ν(t)=

Άρα υπάρχουν c(ν,k)=│s(ν,k)│ μεταθέσεις ν στοιχείων με κ κύκλους ανεξάρτητα από το μήκος τους.

ΜΕΤΑΘΕΣΕΙΣ ΜΕ ΚΥΚΛΟΥΣ ΚΑΘΟΡΙΣΜΕΝΩΝ ΜΗΚΟΥΣ

Πρόβλημα

Πόσες μεταθέσεις ν στοιχείων υπάρχουν με κ κύκλους από τους οποίους κανένας δεν έχει μήκος μικρότερο του r ;

Λύση

Η γεννήτρια έστω s_ν,r(t), του ζητούμενου αριθμού των μεταθέσεων προκύπτει από (5.7) αν θέσουμε t_i=0, i=1,2,…r-1 και t_i=t, i=r, r+1,… ν

Cν (0,…0,t,…t) ≡ Sν,r(t) .

Μετά από πράξεις s_ν,r (t)= , και │s(ν,k,r)│ είναι ο ζητούμενος αριθμός των μεταθέσεων.

ΔΙΑΤΕΤΑΓΜΕΝΕΣ ΚΥΚΛΙΚΕΣ ΜΕΤΑΘΕΣΕΙΣ

Κατά τη μελέτη προβλημάτων απαριθμήσεως μεταθέσεων στις προηγούμενες παραγράφους οι κύκλοι στους οποίους αναλύεται μία μετάθεση διακρίνονται μόνο αναφορικά με το μήκος τους. Είναι δυνατό όμως να προχωρήσουμε ακόμα και να θεωρήσουμε και κάποιο είδος διατάξεως των στοιχείων του κύκλου. Λαμβάνοντας υπόψη την παραδοχή ότι το μικρότερο στοιχείο γράφεται πάντα πρώτο σε ένα κύκλο μήκους r υπάρχουν (r-1)! διατάξεις των στοιχείων του.

Έτσι αν Α(κ₁,κ₂,…,κ_ν) είναι ο αριθμός των μεταθέσεων ν στοιχείων της κλάσεως διατεταγμένων κύκλων (κ₁,κ₂,…,κ_ν) με κ₁ + 2 κ₂ + … + ν κ_ν = ν τότε:

Α(κ₁,κ₂,…,κ_ν)=

Και η γεννήτρια:

γράφεται (5.1)

όπου η άθροιση λαμβάνεται για όλες τις ακέραιες μη αρνητικές τιμές κ₁,κ₂,…,κ_ν με κ₁ + 2 κ₂ + … + ν κ_ν = ν.

Η εκθετική γεννήτρια των Α_ν είναι η:

(5.2)

ΜΕΤΑΘΕΣΕΙΣ ΜΕ ΚΑΘΟΡΙΣΜΕΝΟ ΑΡΙΘΜΟ ΔΙΑΤΕΤΑΓΜΕΝΩΝ ΚΥΚΛΩΝ

Πρόβλημα

Πόσες μεταθέσεις ν στοιχείων υπάρχουν με κ διατεταγμένους κύκλους ανεξάρτητα από το μήκος τους;

Λύσεις

Αν στην (5.1) θέσουμε t_i=t, i=1,2,…,ν, λαμβάνουμε τη γεννήτρια έστω α_ν(t), του ζητούμενου αριθμού των μεταθέσεων :

Α_ν(t,t,…,t)α_ν(t)

Από την (5.2) με t_i=t έχουμε για την α_ν(t) τη σχέση:

η οποία τελικά γράφεται:

άρα

και s(ν,k) 0είναι ο ζητούμενος αριθμός.

ΒΙΒΛΙΟΓΡΑΦΙΑ:

1)Σημειώσεις ανώτερων μαθηματικών , τόμος 1, γ. Τζιβανίδη

2)Εισαγωγή στη συνδυαστική, Χαραλάμπους Α. Χαραλαμπίδη εντ. Υφηγητή του πανεπιστημίου Αθηνών , Αθήνα 1978

ΠΙΤΣΑ ΔΕΣΠΟΙΝΑ Α.Μ. 3857