Правило суммы

Если элемент [math]a[/math] можно выбрать [math]m[/math] способами, и элемент [math]b[/math] - [math]n[/math] способами, то выбор "или [math]a[/math] или [math]b[/math]" можно произвести [math]m + n[/math] способами.

Обобщенное правило суммы

Если некоторое способы выборки элемента [math]a[/math] совпадают со способами выбора элемента [math]b[/math], то такую выборку можно совершить [math]m + n - k[/math] способами, где [math]k[/math] - число совпадающих способов для [math]a[/math] и [math]b[/math].

Правило произведения

Если элемент [math]a[/math] можно выбрать [math]m[/math] способами, и элемент [math]b[/math] - [math]n[/math] способами, то пару [math](a, b)[/math] можно выбрать [math]m \cdot n[/math] способами. (Пара [math](a, b)[/math] отличается от пары [math](b, a)[/math]).


Задачи

Задача 1

В алфавите 33 буквы. Сколько слов, содержащих 5 букв можно составить так, чтобы не было двух идущих подряд одинаковых букв?

  • Первую букву можно выбрать 33 способами
  • Остальные можно выбрать только 32 способами, т.к. не может быть двух одинаковых букв, идущих подряд.
  • Ответ: 33 * 32 * 32 * 32 * 32

Задача 2

Сколькими способами можно поставить на шахматную доску размера 8 * 8 белую и черную ладьи так, чтобы они не били друг друга?

  • 64 - 1-ю ладью можно поставить на любую клетку
  • 49 - ладья 1 бьёт 14 полей и на одном стоит, поэтому остается 64 - 15 полей
  • Ответ: 64 * 49

Задача 3

Сколькими способами можно поставить 2х королей на шахматную доску 8 * 8?

Рассмотрим несколько случаев

  • Если король стоит в углу, то он бьёт 3 поля и стоит на одном - остается 60 клеток для второго;
  • Если король стоит на краю доски, но не в углу (24 поля), то он бьёт 5 полей и стоит на одном - остается 58 клеток;
  • Если не на краю доски (36 полей), то он бьёт 8 полей и стоит на одном - остается 55 клеток.

Ответ: 4 * 60 + 24 * 58 + 36 * 55

Sources

  • Виленкин Н.Я. Комбинаторика. М., Наука, 1969.
  • Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки, 1994.
  • Виленкин Н.Я., Комбинаторика. Статья в журнале "Квант", 1 номер 1971 год. http://kvant.mccme.ru/1971/01/kombinatorika.htm