გადალაგება

გადალაგება კომბინატორიკაში — სიმრავლის ელემენტების ისეთი გადანაცვლება, რომელშიც არც ერთი ელემენტი არ ემთხვევა თავისი პოზიციის ნომერს.

$n$ -ელემენტიანი სიმრავლის გადალაგებების რაოდენობა ცნობილია, როგორც $n$ -ის ქვეფაქტორიალი, ან გადალაგების $n$ -ური წევრი და აღნიშნავენ, როგორც: !n, D_n ან d_n.

დამტკიცებადია, რომ $!n=n!/e$ დამრგვალებული უახლოეს მთელ რიცხვამდე, სადაც $e$ არის ეილერის რიცხვი.

გადალაგებების ამოცანა პირველად განიხილა პიერ რეიმონდ დე მონტმორტმა 1708 წელს და ამოხსნა 1713 წელს, ამავე დროს ნიკოლას ბერნულიმაც.

მაგალითი[რედაქტირება | წყაროს რედაქტირება]

24 გადანაცვლებიდან გამოკვეთილია 9 გადალაგება

დავუშვათ, მასწავლებელმა ტესტირება ჩაუტარა $4-A,B,C,D$ სტუდენტს და სურს, რომ მათ ერთმანეთის ტესტები შეაფასონ. ცხადია, რომ მას არ უნდა რომელიმე სტუდენტმა თავისი ნაშრომი მიიღოს. კითხვა შემდეგია: რამდენი გზა არსებობს ტესტების დარიგებისა ისეთი, რომ არც ერთმა სტუდენტმა თავისი ნაშრომი არ მიიღოს? $4!=24$ შესაძლებელი გადანაცვლებიდან

ABCD,	ABDC,	ACBD,	ACDB,	ADBC,	ADCB,
BACD,	BADC,	BCAD,	BCDA,	BDAC,	BDCA,
CABD,	CADB,	CBAD,	CBDA,	CDAB,	CDBA,
DABC,	DACB,	DBAC,	DBCA,	DCAB,	DCBA.

არსებობს მხოლოდ 9 გადალაგება (აღნიშნულია ლურჯად) და სხვა გადანაცვლებებში ერთი მაინც სტუდენტი არსებობს, რომელიც თავის ნაშრომს (ანუ აკრძალულს) იღებს მასწავლებლისგან.

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

გადალაგებების გამოანგარიშება[რედაქტირება | წყაროს რედაქტირება]

დავუშვათ, $n$ ადამიანს, გადანომრილი $1$ -დან $n$ -ის ჩათვლით, სურს დაიხუროს ასევე $n$ ქუდი, გადანომრილი ასევე $1$ -დან $n$ -ის ჩათვლით, ისე, რომ არც ერთი ადამიანი თავისი ნომრის ქუდს არ იხურავდეს. ვთქვათ, პირველი ადამიანი იხურავს $i$ -ურ ქუდს. $i$ -ური ქუდის ამორჩევის სულ $(n-1)$ ვარიანტია, რადგან მხოლოდ პირველი ქუდის დახურვა არ შეუძლია მას. ამის შემდეგ, ამოცანა შეიძლება ორ ნაწილად გავყოთ $i$ -ური ადამიანის არჩევნის მიხედვით:

თუ $i$ -ურმა ადამიანმა საპასუხოდაც პირველი ქუდი აიღო, მაშინ ორი ადამიანი და ორი ქუდი მოგვარდა, დაგვრჩა გადავალაგოთ $(n-2)$ ადამიანი და $(n-2)$ ქუდი, ანუ გვაქვს $(n-2)$ გადალაგება.
თუ $i$ -ურმა ადამიანმა პირველი არ აიღო, მაშინ გვექნება $n-1$ გადალაგება. რადგან პირველი არ გვაქვს, მე- $2$ ადამიანი ვერ აიღებს მე- $2$ ქუდს, მე- $3$ ადამიანი ვერ აიღებს მე- $3$ -ს, $i$ -ური ვერ აიღებს პირველ ქუდს (რადგან ეს ვარიანტი უკვე განვიხილეთ) $(i+1)$ -ური ვერ აიღებს $(i+1)$ -ურ ქუდს და ა.შ. ანუ დაგვრჩა $(n-1)$ ადამიანი, და თითოეულს ერთი აკრძალული ქუდი აქვს, შესაბამისად გვაქვს $(n-1)$ გადალაგება.

აქედან გამომდინარეობს შემდეგი რეკურენტული ფორმულა:

!n=(n-1)({!(n-1)}+{!(n-2)}).\,

სადაც $!0=1$ და $!1=0$ .

ლიტერატურა[რედაქტირება | წყაროს რედაქტირება]

de Montmort, P. R. (1708). Essay d'analyse sur les jeux de hazard. Paris: Jacque Quillau. Seconde Edition, Revue & augmentée de plusieurs Lettres. Paris: Jacque Quillau. 1713.
Hassani, M. "Derangements and Applications." J. Integer Seq. 6, No. 03.1.2, 1–8, 2003