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

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

Если множество содержит 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-значных чисел, все цифры в которых нечётны и различны?

Сочетания

- число k-элементных подмножеств n-элементного множества (читается как «число сочетаний из n по k»).

Для нахождения количества сочетаний без повторений воспользуемся формулой для размещений без повторений.

Упорядоченных наборов k элементов из n существует n!/(n-k)! Если будем рассматривать неупорядоченные наборы, то каждый из них сосчитаем по k! раз.

Поэтому неупорядоченных наборов в k! раз меньше, чем упорядоченных.

Поэтому количество неупорядоченных наборов вычисляется по формуле: n!/((n-k)!k!).

Пример.

Сколько способов выбрать трёх дежурных из 25 человек?

Можно вычислять по формуле: 25!/(22!∙3!)

Можно и с помощью логических рассуждений. Первого дежурного можно выбрать 25 способами, второго – 24 способами, третьего – 22 способами. Всего получаем 25 ∙ 24 ∙ 22 способа.

Переход к дополнению

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

Пример.

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