Правило суммы
Если элемент $a$ можно выбрать $m$ способами, и элемент $b$ - $n$ способами, то выбор “или $a$ или $b$” можно произвести $m + n$ способами.
Обобщенное правило суммы
Если некоторое способы выборки элемента $a$ совпадают со способами выбора элемента $b$, то такую выборку можно совершить $m + n - k$ способами, где $k$ - число совпадающих способов для $a$ и $b$.
Правило произведения
Если элемент $a$ можно выбрать $m$ способами, и элемент $b$ - $n$ способами, то пару $(a, b)$ можно выбрать $m \cdot n$ способами. (Пара $(a, b)$ отличается от пары $(b, a)$).
Задачи
Задача 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