პერმუტაცია

მოცემული A = (a1; a2; …; a(n)) მიმდევრობის პერმუტაცია მისი ელემენტების გადანაცვლებას  ეწოდება (ლათინური სიტყვიდან “permutare” – გაცვლა.  მაგალითად, A = (a1; a2; a3; a4; a5) მიმდევრობის ერთ-ერთი პერმუტაციის შედეგია (a5; a1; a2; a4; a3), ან (a1; a2; a3; a5; a4),  ან (a3; a2; a5; a1; a4). თვით ეს მიმდევრობაც (a1; a2; a3; a4; a5) A მიმდევრობის პერმუტაციის შედეგია, რომელიც
ყველა ელემენტს თავის ადგილზე ტოვებს.  პერმუტაციათა აღწერის სხვადასხვა მეთოდი არსებობს, მაგრამ ხშირად მათ რიცხვთა მიმდევრობით გამოსახავენ ხოლმე, რომელიც გვიჩვენებს, თუ რომელ პოზიციაზე უნდა გადავიდეს საწყისი მიმდევრობის ესა თუ ის
ელემენტი. მაგალითად, D = (2; 3; 5; 4; 1) პერმუტაციით A მიმდევრობა გადავა (a5; a1; a2; a4; a3) მიმდევრობაში:
მისი პირველი ელემენტი გადავა მეორე ადგილზე, მეორე – მესამეზე, მესამე – მეხუთეზე, მეოთხე ისევე მეოთხეზე
დარჩება და მეხუთე გადავა პირველ ადგილზე. ანალოგიურად, P = (4; 2; 1; 5; 3) პერმუტაციით A მიმდევრობის
ელემენტები გადავა (a3; a2; a5; a1; a4) მიმდევრობაში, ხოლო (1; 2; 3; 4; 5) კი საწყის მიმდევრობას უცვლელს და-
ტოვებს.

 

მათემატიკური ინდუქციის გამოყენებით დავამტკიცოთ, რომ n ელემენტიანი მიმდევრობის n! სხვა-
დასხვა პერმუტაცია არსებობს.

 

ზოგადად  დავუშვათ რომ n-1 ელემენტზე ყველა შესაძლო პერმუტაცია არის (n-1)! . ხოლო რაც შეეხება მე-n  ელემენტს , ჩვენ გვაქვს n-1 ელემენტის შემთხვევაში n ცალი ჩასამატებელი ადგილი , ანუ შეგვიძლია n ცალ ადგილას ჩავამატოთ მე-n  ელემენტი ანუ          (n-1)! * n = n!

 

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s