Основные понятия комбинаторики

Основные понятия комбинаторики

Решить комбинаторную задачу - это значит выписать все возможные комбинации, составленные из чисел, слов, предметов и др., отвечающих условию задачи.

Произведение всех последовательных натуральных чисел от 1 до n называется факториалом и обозначается n!

n! = 1 · 2 · 3 · ... · n.

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

Пример 1. При расследовании хищения установлено, что у преступника семизначный телефонный номер, в котором ни одна цифра не повторяется, и нет нуля. Следователь, полагая, что перебор этих номеров потребует одного-двух часов, доложил о раскрытии преступления. Прав ли он?

Решение. Число номеров равно числу размещений из 9 элементов по 7, т.е. равно По формуле получаем номеров.

Даже если на проверку одного номера тратить 1 минуту, то на все уйдет 3024 часа или 126 суток. Таким образом, следователь – не прав.

Сочетаниями из n элементов по m называются такие соединения, которые отличаются друг от друга хотя бы одним элементом. (Подмножества, отличающиеся друг от друга только порядком следования элементов, не считаются различными.)

Число сочетаний из n элементов по m обозначается символом и вычисляется по формуле:

Пример 2. В штате прокуратуры областного центра имеется 16 следователей. Сколькими способами можно выбрать 2 из них для проверки оперативной информации о готовящемся преступлении?

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

Перестановками из n элементов называются такие соединения из n элементов, которые отличаются друг от друга лишь порядком следования элементов.

Пример 3. Замок сейфа открывается, если введена правильная комбинация. Преступник пытается открыть сейф, набирая код наудачу. Он знает, что код состоит из цифр 1, 2, 3, 4, 5, 6 при условии, что все числа не повторяются и последней является 5. Сколько попыток ему придется сделать.

Решение. Так как число пять должно стоять на последнем месте, то остальные пять цифр могут стоять на оставшихся местах в любом порядке. Следовательно, количество кодов из шестизначных чисел, с пятеркой на конце, равно числу перестановок из пяти элементов, т.е. .