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

                                            36
Комбинаторика
                                        x1 +x 2 +x 3 =20 ,
                                  x1 ≥1, x 2 ≥10, x 3 ≥0 ,
число Ν (α 3 ) - с числом наборов (x1 , x 2 , x 3 ), для которых
                                        x1 +x 2 +x 3 =20 ,
                                  x1 ≥1, x 2 ≥0, x3 ≥10 ,
число Ν (α1 , α 2 ) - с числом наборов (x1 , x 2 , x 3 ), для которых
                                        x1 +x 2 +x 3 =20 ,
                                 x1 ≥10, x 2 ≥10, x 3 ≥0 ,
число Ν (α1 , α 3 ) - с числом наборов (x1 , x 2 , x 3 ), для которых
                                        x1 +x 2 +x 3 =20 ,
                                  x1 ≥10, x 2 ≥0, x3 ≥10 ,
число Ν (α 2 , α 3 ) - с числом наборов (x1 , x 2 , x 3 ), для которых
                                        x1 +x 2 +x 3 =20 ,
                                  x1 ≥1, x 2 ≥10, x3 ≥10 ,
число Ν (α1 , α 2 , α 3 ) - с числом наборов (x1 , x 2 , x 3 ), для которых
                                        x1 +x 2 +x 3 =20 ,
                                 x1 ≥10, x 2 ≥10, x3 ≥10 .
      Используя подходящие замены переменных и формулу для числа
сочетаний с повторениями, найдем
                                                                    12!
                       Ν (α1 ) =C 3
                                    20 −10      10           10
                                            =C10  +3−1 =C12 =            =66 ,
                                                                  10!2!
                                                                    11!
                        Ν (α 2 ) =C 3
                                      20 −11
                                             =C99+3−1 =C11    9
                                                                =       =55 ,
                                                                   9!2!
                                                                    11!
                        Ν (α 3 ) =C 3
                                      20 −11
                                             =C 99+3−1 =C11   9
                                                                =       =55 ,
                                                                   9!2!
                                    Ν (α1 , α 2 ) =C 3
                                                       20 −20
                                                               =1 ,
                                Ν (α1 , α 3 ) =C 3
                                                 20−20
                                                         =1 ,
                                Ν (α 2 , α 3 )
                                                20−21
                                             =C 3        =0 ,
                                   Ν (α1 , α 2 , α 3 ) =0 .
     Итак,
Ν 0 =Ν −Ν (α1 )−Ν (α 2 )−Ν (α 3 ) +Ν (α1 , α 2 ) +Ν (α1 , α 3 ) +Ν (α 2 , α 3 ) −
−Ν (α1 ,α 2 , α 3 ) =210 −66 −55 −55 +1 +1 =36 .

     Задача 3. К обеду за круглым столом приглашены 4 пары враждующих
рыцарей. Сколькими способами их можно разместить за столом так, чтобы
никакие из двух враждующих рыцарей не сидели рядом?
     Решение. Обозначим через Χ множество всевозможных размещений
рыцарей за столом и введем три свойства для элементов данного множества: