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

Размещения. Размещениями из 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 способов.

< Предыдущая		Следующая >