გადალაგება

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
Jump to navigation Jump to search

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

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

დამტკიცებადია, რომ დამრგვალებული უახლოეს მთელ რიცხვამდე, სადაც არის ეილერის რიცხვი.

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

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

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

დავუშვათ, მასწავლებელმა ტესტირება ჩაუტარა სტუდენტს და სურს, რომ მათ ერთმანეთის ტესტები შეაფასონ. ცხადია, რომ მას არ უნდა რომელიმე სტუდენტმა თავისი ნაშრომი მიიღოს. კითხვა შემდეგია: რამდენი გზა არსებობს ტესტების დარიგებისა ისეთი, რომ არც ერთმა სტუდენტმა თავისი ნაშრომი არ მიიღოს? შესაძლებელი გადანაცვლებიდან

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 გადალაგება (აღნიშნულია ლურჯად) და სხვა გადანაცვლებებში ერთი მაინც სტუდენტი არსებობს, რომელიც თავის ნაშრომს (ანუ აკრძალულს) იღებს მასწავლებლისგან.

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

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

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

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

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

სადაც და .

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

  • 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