Дискретная математика. Азарнова Т.В - 37 стр.

                                                 37
Комбинаторика
α1 - первая пара враждующих рыцарей сидит рядом, α 2 - вторая пара
враждующих рыцарей сидит рядом, α 3 - третья пара враждующих рыцарей
сидит рядом, α 4 - четвертая пара враждующих рыцарей сидит рядом. Теперь
наша задача найти число Ν 0 элементов в множестве Χ , которые не
обладают ни одним из введенных свойств.
         Число элементов Ν в множестве Χ равно числу перестановок без
повторений из 8 элементов Ν =8! . Для вычисления чисел Ν (α1 ),
Ν (α 2 ), Ν (α 3 ), Ν (α 4 )       мы       рассматриваем               соответствующую            пару
враждующих рыцарей как один объект и находим                                              всевозможные
перестановки 7 объектов, учитывая при этом порядок рыцарей внутри
объединенной пары. Поэтому,
                           Ν (α1 ) =Ν (α 2 ) =Ν (α 3 ) =Ν (α 4 ) =2 ⋅ 7!.
Числа Ν (α1 , α 2 ), Ν (α1 ,α 3 ), Ν (α1 , α 4 ), Ν (α 2 , α 3 ), Ν (α 2 ,α 4 ), Ν (α 3 ,α 4 )
находятся аналогично. Объединяются в одно целое по две пары враждующих
рыцарей и находятся всевозможные перестановки из 6 объектов, при этом
учитывается порядок внутри объединенных пар:
                            Ν (α i , α j ) =2 ⋅ 2 ⋅ 6! i, j =1,2,3,4, i < j .
Аналогично, при нахождении Ν (α1 , α 2 , α 3 ), Ν (α1 , α 2 , α 4 ), Ν (α1 ,α 3 , α 4 ),
Ν (α 2 , α 3 ,α 43 ) объединяются в один объект по три пары враждующих
рыцарей и находятся всевозможные перестановки из пяти объектов с учетом
порядка внутри объединенных пар. Все эти величины равны между собой и
равны 2 ⋅ 2 ⋅ 2 ⋅ 5! .
Последняя искомая величина Ν (α1 , α 2 , α 3 , α 4 ) =2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 4! .
       Итак,
Ν 0 =Ν −Ν (α1 ) −Ν (α 2 ) −Ν (α 3 ) −Ν (α 4 ) −
+Ν (α1 , α 2 ) +Ν (α1 , α 3 ) +Ν (α1 , α 4 ) +Ν (α 2 , α 3 ) +Ν (α 2 , α 4 ) +Ν (α 3 , α 4 ) −
−Ν (α1 , α 2 , α 3 ) −Ν (α1 , α 2 , α 4 ) −Ν (α1 ,α 3 , α 4 ) −Ν (α 2 , α 3 , α 4 ) +
+Ν (α1 , α 2 , α 3 , α 4 ) =8!−4 ⋅ 2 ⋅ 7!+6 ⋅ 2 ⋅ 2 ⋅ 6!−4 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 5!−2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 4!




                          Задачи для самостоятельного решения.


1. Доказать тождества:
                  n
            a)   ∑ C nk   =2 n , n ≥0;
                 k =0

                  n
            b)   ∑ kCnk    =n2 n−1 ;
                 k =0