Основные комбинаторные формулы

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

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

, (1)

где (считается, что 0! = 1).

 

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

Решение. В этом случае надо найти число размещений (без повторений) из 25 элементов по 4, так как здесь играет роль и то, кто будет выбран в руковод­ство общества, и то, какие посты займут выбранные.

Ответ: .

 

 

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

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

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

(2)

 

 

Пример 2.2. Для запирания сейфов и автоматических камер хранения применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое «тайное слово». Пусть на диск нанесено 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?

Решение. Общее число возможных комбинаций можно найти по формуле (2)

.

Число неудачных попыток — 248 832 – 1 = 248 831.

Ответ: 248 831.

 

 

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

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

, (3)

где .

Пример 2.3. Покупая карточку лотереи «Спортлото», игрок должен зачеркнуть 6 из 49 возможных чисел от 1 до 49. Сколько возможных комбинаций можно составить из 49 по 6, если порядок чисел безразличен?

Решение. Число возможных комбинаций можно рассчитать по формуле (3)

.

Ответ: N = 13 983 816.

 

 

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

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

.

В сочетаниях с повторениями m может быть и больше n.

 

 

Пример 2.4. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Решение. Число различных покупок равно числу сочетаний с повторениями из 4 по 7:

.

Ответ: Из пирожных 4 сортов 7 пирожных можно выбрать 120 способами.

 

 

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

Число перестановок из n элементов обозначается символом , это то же самое, что число размещений из n элементов по n в каждом, поэтому

.

Пример 2.5. Сколько существует способов составления списка 10 деловых звонков случайным образом?

Решение. Количество способов составления списка из 10 звонков будет равно числу перестановок из 10 элементов:

.

Ответ: Число способов составления списка из 10 звонков равно 3 628 800.

 

 

Перестановки с повторениями. Пусть имеются n элементов, среди которых элементов одного типа, элементов другого типа, элементов
l -го типа . Число перестановок из этих n элементов равно числу перестановок с повторениями, обозначается и вычисляется по формуле

.

 

 

Пример 2.6. Десять приезжих мужчин размещаются в гостинице в двух трехместных и одном четырехместном номерах. Сколько существует способов их размещения?

Решение.

Ответ: Существует 4200 способов.