Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 74 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

74
Используя метод включения–исключения, обозначим через
α свойст-
во перестановки, заключающееся в том, что число
α стоит на своем месте, а
через N(
α) – количество перестановок, обладающих этим свойством. Nαβ –
число перестановок, обладающих свойством
αβ; N
(0)
– число перестановок,
не обладающих ни одним из перечисленных свойств (1), (2), (3), (4) и (5),
т. е. число перестановок, в которых ни одно число не стоит на своем месте.
По формуле включения-исключения имеем
N
(0)
= N – N
1
– N
2
– N
3
– N
4
– N
5
+ N
12
+ ... +
+ N
45
– N
123
– ... – N
345
+ N
1234
+ ... + N
2345
– N
12345
, (11)
где N = P
5
– общее число всех перестановок из пяти элементов.
Задача облегчается тем, что свойства (1), (2), (3), (4) и (5) совершенно
равноправны, поэтому ясно, что N
1
= N
2
= N
3
= N
4
= = N
5
. Точно так же имеем
N
12
= N
23
= ... = N
45
. Но число пар, которые можно выбрать из чисел 1, 2, 3, 4,
5 – C
2
5 .
Свойства (1, 2) и (2,1) совпадают, поэтому порядок нас не интересу-
ет. Точно так же имеем С
3
5
троек, C
4
5
четверок, C
5
5
пятерок. Формулу (11)
перепишем следующим образом:
N
(0)
= N – C
1
5
N
(1)
+ C
2
5
N
(2)
– C
3
5
N
(3)
+ C
4
5
N
(4)
– C
5
5
N
(5)
, (12)
где N
(k)
– количество перестановок, в которых заданные k чисел остались
на своих местах; N
(1)
– одно число на своем месте, остальные переставляют-
ся, т. е. P
4
= 4! = 24. Следовательно, N
(1)
= = 24 = P
4
; N
(2)
– два числа на мес-
те, три переставляются; N
(2)
= = P
3
= 6, аналогично N
(3)
= P
2
= 2; N
(4)
= P
1
=1;
N
(5)
= P
0
= 1. Подставляем эти значения в формулу (12).
N
(0)
= P
5
– C
1
5
P
4
+ C
2
5
P
3
– C
3
5
P
2
+ C
4
5
P
1
– C
5
5
P
0
=
120 – 5
×24 + 10×6 – 10×2 + 5×1 –1×1 = 44.
Итак, в 44 случаях из 120 ни одно число не стоит на своем месте.
Так же можно найти, во скольких случаях ровно один элемент стоит на
своем месте. Если это первый элемент, то
N
(0)
= P
4
– C
1
4
P
3
+ C
2
4
P
2
– C
3
4
P
1
+ C
4
4
P
0
= 9 способов. 
       Используя метод включения–исключения, обозначим через α свойст-
во перестановки, заключающееся в том, что число α стоит на своем месте, а
через N(α) – количество перестановок, обладающих этим свойством. Nαβ –
число перестановок, обладающих свойством αβ; N(0) – число перестановок,
не обладающих ни одним из перечисленных свойств (1), (2), (3), (4) и (5),
т. е. число перестановок, в которых ни одно число не стоит на своем месте.
       По формуле включения-исключения имеем
       N(0) = N – N1 – N2 – N3 – N4 – N5 + N12 + ... +
                       + N45 – N123 – ... – N345 + N1234 + ... + N2345 – N12345, (11)
где N = P5 – общее число всех перестановок из пяти элементов.
       Задача облегчается тем, что свойства (1), (2), (3), (4) и (5) совершенно
равноправны, поэтому ясно, что N1 = N2 = N3 = N4 = = N5. Точно так же имеем
N12 = N23 = ... = N45. Но число пар, которые можно выбрать из чисел 1, 2, 3, 4,
5 – C25 . Свойства (1, 2) и (2,1) совпадают, поэтому порядок нас не интересу-
                             3                   4            5
ет. Точно так же имеем С троек, C                  четверок, C пятерок. Формулу (11)
                             5                   5            5

перепишем следующим образом:
            1          2             3            4       5
N(0) = N – C N(1) + C N(2) – C N(3) + C N(4) – C N(5),            (12)
            5          5             5            5       5

где N(k) – количество перестановок, в которых заданные k чисел остались
на своих местах; N(1) – одно число на своем месте, остальные переставляют-
ся, т. е. P4 = 4! = 24. Следовательно, N(1) = = 24 = P4; N(2) – два числа на мес-
те, три переставляются; N(2) = = P3= 6, аналогично N(3) = P2 = 2; N(4) = P1=1;
N(5) = P0 = 1. Подставляем эти значения в формулу (12).
                            1            2            3       4    5
                 N(0) = P5 – C P4 + C P3 – C P2 + C P1 – C P0 =
                            5            5            5       5    5

                 120 – 5×24 + 10×6 – 10×2 + 5×1 –1×1 = 44.
Итак, в 44 случаях из 120 ни одно число не стоит на своем месте.
   Так же можно найти, во скольких случаях ровно один элемент стоит на
своем месте. Если это первый элемент, то
             1         2         3           4
N(0) = P4 – C P3 + C P2 – C P1 + C P0 = 9 способов.
             4         4         4           4




                                             74

Страницы