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

   2       2
= m (m + 1) .
      4

             3.6. Правила суммы и произведений

      Комбинаторные задачи бывают самых разных видов, но большинство
задач решается с помощью правила суммы и правила произведения.
      Часто удается разбить все изучаемые комбинации на несколько клас-
сов, причем каждая комбинация входит в один и только один класс. Ясно,
что в этом случае общее число комбинаций равно сумме чисел комбинаций
во всех классах. Это утверждение и называется правилом суммы.
      Правило суммы: если объект А можно выбрать m способами, а объ-
ект В другими n способами, то выбор “либо А, либо В” может быть осуще-
ствлен m + n способами.
      Второе правило – правило произведения. Часто при составлении ком-
бинации из двух элементов известно, сколькими способами можно выбрать
1-й элемент, и сколькими способами второй, причем число способов выбора
второго элемента не зависит от того, как именно выбран первый элемент.
      Правило произведения: если объект А выбран m способами и после
каждого из таких выборов, объект В, в свою очередь может быть выбран n
способами, то выбор «A и B» в указанном порядке может быть осуществлен
m × n способами.
      Задача 1 (о шашках)
      Сколькими способами можно поставить на доску две шашки – белую
и черную – так, чтобы белая шашка могла бить черную?
      Правила игры в шашки известны.
      Сложность этой задачи состоит в том, что для разных положений бе-
лой шашки есть разное число положений черной шашки, при которых эту
шашку можно бить (рис. 55).
                          5       5       5       6

                     1       2            2       1

                         2       4            4       2

                     2       4            4       2

                         2       4            4       2


                                     62