გადალაგება: განსხვავება გადახედვებს შორის

[შეუმოწმებელი ვერსია]

შიგთავსი ამოიშალა შიგთავსი დაემატა

შიდახაზური

15:16, 24 ივლისი 2020-ის ვერსია

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

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

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

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

მაგალითი

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

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

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

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

გადალაგებების გამოანგარიშება

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

თუ $i$ - ურმა ადამიანმა საპასუხოდაც პირველი ქუდი აიღო, მაშინ ორი ადამიანი და ორი ქუდი მოგვარდა, დაგვრჩა გადავალაგოთ $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$ .

@@ ხაზი 2: / ხაზი 2: @@
 კომბინატორიკაში, '''გადალაგება''' არის სიმრავლის ელემენტების ისეთი გადანაცვლება, რომელშიც არც ერთი ელემენტი არ ემთხვევა თავისი პოზიციის ნომერს.
-n-ელემენტიანი სიმრავლის გადალაგებების რაოდენობა ცნობილია, როგორც n-ის ქვეფაქტორიალი, ან გადალაგების n-ური წევრი და აღნიშნავენ, როგორც: !n, Dn ან dn.
+<math>n</math>-ელემენტიანი სიმრავლის გადალაგებების რაოდენობა ცნობილია, როგორც <math>n</math>-ის ქვეფაქტორიალი, ან გადალაგების <math>n</math>-ური წევრი და აღნიშნავენ, როგორც: !''n,'' ''D<sub>n</sub>'' ან ''d<sub>n</sub>''.
-დამტკიცებადია, რომ !n = n! / e, სადაც e არის ეილერის რიცხვი.
+დამტკიცებადია, რომ <math>!n = n! / e</math>, სადაც <math>e</math> არის ეილერის რიცხვი.
 გადალაგებების ამოცანა პირველად განიხილა პიერ რეიმონდ დე მონტმორტმა 1708 წელს და ამოხსნა 1713 წელს, ამავე დროს ნიკოლას ბერნულიმაც.
@@ ხაზი 10: / ხაზი 10: @@
 == მაგალითი ==
 [[ფაილი:Derangement4.png|მარჯვნივ|მინი| 24 გადანაცვლებიდან გამოკვეთილია 9 გადალაგება ]]
-დავუშვათ, მასწავლებელმა ტესტირება ჩაუტარა 4 - A, B, C, D სტუდენტს და სურს, რომ მათ ერთმანეთის ტესტები შეაფასონ. ცხადია, რომ მას არ უნდა რომელიმე სტუდენტმა თავისი ნაშრომი მიიღოს. კითხვა შემდეგია: რამდენი გზა არსებობს ტესტების დარიგებისა ისეთი, რომ არც ერთმა სტუდენტმა თავისი ნაშრომი არ მიიღოს? 4! = 24 შესაძლებელი გადანაცვლებიდან
+დავუშვათ, მასწავლებელმა ტესტირება ჩაუტარა <math>4 - A, B, C, D</math> სტუდენტს და სურს, რომ მათ ერთმანეთის ტესტები შეაფასონ. ცხადია, რომ მას არ უნდა რომელიმე სტუდენტმა თავისი ნაშრომი მიიღოს. კითხვა შემდეგია: რამდენი გზა არსებობს ტესტების დარიგებისა ისეთი, რომ არც ერთმა სტუდენტმა თავისი ნაშრომი არ მიიღოს? <math>4! = 24</math> შესაძლებელი გადანაცვლებიდან
 არსებობს მხოლოდ 9 გადალაგება (იხ. სურათი) და სხვა გადანაცვლებებში ერთი მაინც სტუდენტი არსებობს, რომელიც თავის ნაშრომს (ანუ აკრძალულს) იღებს მასწავლებლისგან.
@@ ხაზი 17: / ხაზი 17: @@
 == გადალაგებების გამოანგარიშება ==
-დავუშვათ, დგას n ადამიანი, გადანომრილი 1 - დან n - ის ჩათვლით, ასევე n ქუდი, გადანომრილი ასევე 1 - დან n - ის ჩათვლით. ვიპოვოთ იმ გზების რაოდენობა, რომლებშიც არც ერთი ადამიანი თავისი ნომრის ქუდს არ იხურავს. დავუშვათ, პირველი ადამიანი იხურავს i-ურ ქუდს. i-ური ქუდის ამორჩევის სულ (n - 1) ვარიანტია, რადგან მხოლოდ პირველი ქუდის დახურვა არ შეუძლია. ამის შემდეგ ამოცანა შეიძლება ორ ნაწილად გავყოთ, i - ური ადამიანის არჩევანის მიხედვით.
+დავუშვათ, დგას <math>n</math> ადამიანი, გადანომრილი <math>1</math> - დან <math>n</math> - ის ჩათვლით, ასევე n ქუდი, გადანომრილი ასევე <math>1</math> - დან <math>n</math> - ის ჩათვლით. ვიპოვოთ იმ გზების რაოდენობა, რომლებშიც არც ერთი ადამიანი თავისი ნომრის ქუდს არ იხურავს. დავუშვათ, პირველი ადამიანი იხურავს <math>i</math>-ურ ქუდს. <math>i</math>-ური ქუდის ამორჩევის სულ <math>(n - 1)</math> ვარიანტია, რადგან მხოლოდ პირველი ქუდის დახურვა არ შეუძლია. ამის შემდეგ ამოცანა შეიძლება ორ ნაწილად გავყოთ, <math>i</math> - ური ადამიანის არჩევანის მიხედვით.
-#  თუ i - ურმა ადამიანმა საპასუხოდაც პირველი ქუდი აიღო, მაშინ ორი ადამიანი და ორი ქუდი მოგვარდა, დაგვრჩა გადავალაგოთ n - 2 ადამიანი და n - 2 ქუდი.
+#  თუ <math>i</math> - ურმა ადამიანმა საპასუხოდაც პირველი ქუდი აიღო, მაშინ ორი ადამიანი და ორი ქუდი მოგვარდა, დაგვრჩა გადავალაგოთ <math>n - 2</math> ადამიანი და <math>n - 2</math> ქუდი.
-#  თუ i - ურმა ადამიანმა პირველი არ აიღო, მაშინ გვექნება n - 1 გადალაგება. რადგან პირველი არ გვაქვს, მე-2 ადამიანი ვერ აიღებს მე-2 ქუდს, მე-3 ადამიანი ვერ აიღებს მე-3-ს, i-ურ ვერ აიღებს პირველ ქუდს (რადგან ეს ვარიანტი უკვე განვიხილეთ) (i + 1) - ურ ვერ აიღებს (i + 1) ურ ქუდს. ანუ დაგვრჩა (n - 1) ადამიანი, და თითოეულს ერთი აკრძალული ქუდი აქვს, შესაბამისად გვაქვს (n - 1) გადალაგება.
+#  თუ <math>i</math> - ურმა ადამიანმა პირველი არ აიღო, მაშინ გვექნება <math>n - 1</math> გადალაგება. რადგან პირველი არ გვაქვს, მე-<math>2</math> ადამიანი ვერ აიღებს მე-<math>2</math> ქუდს, მე-<math>3</math> ადამიანი ვერ აიღებს მე-<math>3</math>-ს, i-ურ ვერ აიღებს პირველ ქუდს (რადგან ეს ვარიანტი უკვე განვიხილეთ) <math>(i + 1)</math> - ურ ვერ აიღებს (i + 1) ურ ქუდს. ანუ დაგვრჩა (n - 1) ადამიანი, და თითოეულს ერთი აკრძალული ქუდი აქვს, შესაბამისად გვაქვს <math>(n - 1)</math> გადალაგება.
 აქედან გამომდინარეობს შემდეგი რეკურენტული ფორმულა:
@@ ხაზი 26: / ხაზი 26: @@
 : <math>!n = (n - 1) ({!(n-1)} + {!(n-2)}).\,</math>
-სადაც !0 = 1 და !1 = 0.
+სადაც <math>!0 = 1</math> და <math>!1 = 0</math>.
 [[კატეგორია:გადაადგილებები]]