Правило сложения

Идея рассуждения – разбить все варианты на группы, каждая из которых состоит из «одинаково устроенных» комбинаций.

Пример

Сколько способов поставить двух шахматных королей на доску 8х8 так, чтобы они не «били» друг друга?

Решение.

В данном случае количество полей, которое «бьёт» король, зависит от его положения на доске.

Если он в углу (4 варианта), то для второго короля свободны 60 полей, если у края доски (24 варианта), то свободны 58 полей, а если отстоит не в углу и не у края (36 вариантов), то свободны 55 полей.

Таким образом, получим 4 × 60 + 24 × 58 + 36 × 55 = 3612. Разделив это количество пополам (по той же причине, что в предыдущем примере), получим 1806.

Перестановки

Перестановкой называют упорядоченный набор чисел 1, 2, 3, … n, возможно, переставленных в другом порядке – например, 3, 2, 1, 4, 5, 6, …, n.

Первый элемент перестановки можно выбрать n способами, тогда второй останется (n-1) способов, на третий – (n-2) способа, и так далее до заключительного элемента, для которого останется ровно один вариант.

Таким образом, количество перестановок равно n(n-1)(n-2)× … × 2×1 = n!

Примечание. n! здесь и далее обозначает произведение всех целых чисел от 1 до n. В задачах по комбинаторике принято оставлять в ответе факториалы, степени, произведения, поскольку число в ответе задачи может оказаться большим, и его вычисление займёт слишком много времени.

Пример.

Сколько способов посадить 5 человек на 5 стульев, по одному человеку на стул?

Размещения с повторениями

Размещение с повторениями – упорядоченный набор элементов, каждый из которых принадлежит данному множеству.

Если множество содержит n элементов, а наборы должны содержать k элементов, то каждый элемент можем выбрать n способами, всего элементов k, поэтому количество размещений с повторениями равно n^k.

Пример.

Сколько существует 4-значных чисел, все цифры в которых нечётны?

Размещения без повторений

Размещение без повторений – упорядоченный набор элементов, каждый из которых принадлежит данному множеству, и при этом все элементы набора должны быть различными.

Если множество содержит n элементов, а наборы должны содержать k элементов, то первый элемент можем выбрать n способами, второй (n-1) способом, и так далее до элемента номер k, его можем выбрать (n – k +1) способом. Поэтому количество размещений без повторений равно n(n - 1)…(n – k +1) = n! / (n-k)!

Пример.

Сколько существует 4-значных чисел, все цифры в которых нечётны и различны?