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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

77
б) если в парах элементы разные, например, (1, 2) и (3, 4,), {1, 2, 3, 4}
=> (1, 2), (3, 4), 5, 6, 7, 8, 9.
В обоих случаях получаем 7 новых элементов, которые можно пере-
ставлять друг с другом P
7
способами. А две пары из 8 можно выбрать C
2
8
способами. Так же доказывается, что количество перестановок, содержащих
k пар, равно P
9–k
. При этом k пар, можно выбрать С
k
8
способами. По фор-
муле включения-исключения получаем, что количество перестановок, не
содержащих ни одной из заданных пар, равно N
(n)
=P
9
– C
1
8
P
8
+ C
2
8
P
7
– C
3
8
P
6
+ C
4
8
P
5
– C
5
8
P
4
+ C
6
8
P
3
– C
7
8
P
2
+ C
8
8
P
1
= 8! [9 –
!1
8
+
!2
7
–
!3
6
+
!4
5
–
!5
4
+
!6
3
–
!7
2
+
!8
1
] = 148 329.
Аналогично доказывается, что количество перестановок из n чисел 1,
2, ... , n не содержащих ни одной из пар (1, 2), (2, 3), ... , (n – 1, n) выражает-
ся формулой
E
n
= P
n
– C
1
1-n
P
n–1
+ C
2
1-n
P
n–2
– C
3
1-n
P
n–3
+ ...+
+(–1)
n–1
C
1-n
1-n
P
1
. (17)
Так же доказывается, что количество перестановок из n элементов,
в которые не входят заданные r < n–1 пар, равно
E
n
= P
n
– C
1
r
P
n–1
+ C
2
r
P
n–2
– C
3
r
P
n–3
+...+
+(–1)
r
C
r
r
P
n–r
. (18)
Если r > n – 1, то
E
n
=P
n
– C
1
1-n
P
n–1
+ C
2
1-n
P
n–2
– ... – (–1)
k
C
k
n
P
n–k
+...+
+ (–1)
n–1
C
1-n
1-n
P
1
= n! [1 –
!1
1
+
!2
1
– ... +
1)!(n
)1(
1n
−
−
−
]
= n D
n–1
. (19)
Задача 3. “Карусель” 
      б) если в парах элементы разные, например, (1, 2) и (3, 4,), {1, 2, 3, 4}
=> (1, 2), (3, 4), 5, 6, 7, 8, 9.
      В обоих случаях получаем 7 новых элементов, которые можно пере-
                                                                                            2
ставлять друг с другом P7 способами. А две пары из 8 можно выбрать C
                                                                                            8

способами. Так же доказывается, что количество перестановок, содержащих
                                                                       k
k пар, равно P9–k. При этом k пар, можно выбрать С                       способами. По фор-
                                                                       8
муле включения-исключения получаем, что количество перестановок, не
                                                                           1     2      3
содержащих ни одной из заданных пар, равно N(n)=P9 – C P8 + C P7 – C P6
                                                                           8     8      8

    4         5              6         7          8            8   7   6   5   4   3
+ C P5 – C P4 + C P3 – C P2 + C P1 = 8! [9 –                     +   –   +   –   +   –
    8         8              8         8          8            1! 2! 3! 4! 5! 6!
 2      1
    + ] = 148 329.
7! 8!
         Аналогично доказывается, что количество перестановок из n чисел 1,
2, ... , n не содержащих ни одной из пар (1, 2), (2, 3), ... , (n – 1, n) выражает-
ся формулой
                   1
        En = Pn – C      Pn–1 + C 2 Pn–2 – C 3 Pn–3 + ...+
                   n -1           n -1       n -1
        +(–1)n–1 C n - 1 P1 .                              (17)
                   n -1
     Так же доказывается, что количество перестановок из n элементов,
в которые не входят заданные r < n–1 пар, равно
        En = Pn – C 1 Pn–1 + C 2 P n–2 – C 3 Pn–3 +...+
                         r             r              r
              +(–1)rC r Pn–r .                                                   (18)
                                r
        Если r > n – 1, то
        En =Pn – C 1            Pn–1 + C 2 Pn–2 – ... – (–1)k C k Pn–k +...+
                         n -1              n -1                 n

                   n–1     n -1             1   1         ( −1) n −1
          + (–1)         C      P = n! [1 –   +   – ... +            ]
                           n -1 1           1! 2!          (n − 1)!
          = n Dn–1.                                                   (19)
        Задача 3. “Карусель”



                                                      77

Страницы