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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

75
Общее количество способов, при которых один элемент стоит на сво-
ем месте, равно 5
×9 = 45, так как С
1
5
= 5. Итак, можно посчитать, что два
элемента стоят на своих местах в 20 случаях, три – в 10 случаях, четыре – в
0 случаях, пять – в 1-м случае:
N
2
= P
3
– C
1
3
P
2
+ C
2
3
P
1
– C
3
3
P
0
= 6 – 3×2 + 3 – 1 = 2,
C
2
5
=
!3!2
!5
= 10, => 2×10 = 20.
N
3
= P
2
– C
1
2
P
1
+ C
2
2
P
0
= 2 – 2 + 1 = 1,
C
3
5
= 10, => 10×1 = 10. N
4
= P
1
– C
1
1
P
0
= 0.
Результат для четырех элементов объясняется тем, что если четыре
элемента стоят на своем месте, то и пятый должен стоять на своем месте.
Итак, 120 разных способов перестановок из
5 элементов распадаются на: 44 перестановки, в которых ни один элемент
не остается на месте, 45 перестановок, в которых ровно один элемент не
меняет своего положения
, 20 перестановок, в которых ровно два элемента
не меняют своего положения, 10 перестановок, в которых ровно три эле-
мента не меняют своего положения, 0 перестановок, в которых ровно четы-
ре элемента не меняют своего положения, 1 перестановка, в которой ровно
пять элементов не меняют своего положения.
120 = 44 + 45 + 20 + 10 + 0 +1.
3.9.2. Общая задача о смещении
1. Число D
n
перестановок из n элементов, при которых ни один эле-
мент не остается в первоначальном положении:
D
(n)
= P
n
– C
1
n
P
n–1
+ C
2
n
P
n–2
–... + (–1)
n
C
n
n
P
0
=
= n![1 –
!1
1
+
!2
1
– ... +
n!
1)(
n
−
] . (13)
2. Число перестановок, в которых ровно r элементов остаются на мес-
те, а остальные n – r меняют свое положение, выражается формулой 
     Общее количество способов, при которых один элемент стоит на сво-
                                              1
ем месте, равно 5×9 = 45, так как С = 5. Итак, можно посчитать, что два
                                              5

элемента стоят на своих местах в 20 случаях, три – в 10 случаях, четыре – в
0 случаях, пять – в 1-м случае:
                          1           2           3
             N2 = P3 – C P2 + C P1 – C P0 = 6 – 3×2 + 3 – 1 = 2,
                          3           3           3

      2
     C = 5! = 10, => 2×10 = 20.
      5 2!3!

                                  1               2
                     N3 = P2 – C P1 + C P0 = 2 – 2 + 1 = 1,
                                  2               2

 3                                        1
C = 10, => 10×1 = 10. N4 = P1 – C P0 = 0.
 5                                        1

      Результат для четырех элементов объясняется тем, что если четыре
элемента стоят на своем месте, то и пятый должен стоять на своем месте.
Итак,       120       разных        способов         перестановок    из
5 элементов распадаются на: 44 перестановки, в которых ни один элемент
не остается на месте, 45 перестановок, в которых ровно один элемент не
меняет своего положения, 20 перестановок, в которых ровно два элемента
не меняют своего положения, 10 перестановок, в которых ровно три эле-
мента не меняют своего положения, 0 перестановок, в которых ровно четы-
ре элемента не меняют своего положения, 1 перестановка, в которой ровно
пять элементов не меняют своего положения.
                         120 = 44 + 45 + 20 + 10 + 0 +1.

                      3.9.2. Общая задача о смещении
     1. Число Dn перестановок из n элементов, при которых ни один эле-
мент не остается в первоначальном положении:
     D(n) = Pn – C 1n Pn–1 + C 2n Pn–2 –... + (–1)n C nn P0 =
                                               n
                  = n![1 – 1 + 1 – ... + ( −1) ] .                    (13)
                           1! 2!            n!
       2. Число перестановок, в которых ровно r элементов остаются на мес-
те, а остальные n – r меняют свое положение, выражается формулой

                                          75

Страницы