1.3. Основные элементы комбинаторики и их число

Комбинации элементов могут быть составлены различными способами, а именно, в виде перестановок, размещений и сочетаний. Эти три вида соединений (комбинаций) являются основными понятиями комбинаторики.

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

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

.

Например, 1!=1

2!= 1·2=2

3!= 1·2·3=6

4!= 1·2·3·4=24 и т.д.

По определению принято, что 0!=1.

Пусть имеется три различных элемента a, b, c. Будем составлять из этих элементов различные комбинации.

1. Размещения

Выберем из трех элементов a, b, c два элемента с учетом их расположения. Получим

a b, b a, b c, c b, a c, c a.

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

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

Например, размещения a b и b a отличаются порядком расположения элементов, а размещения a b и c b отличаются элементами a и c.

Очевидно, что т ≤ n.

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

Пример 1.4. Руководство некоторого банка должно выбрать трех человек из 12 на три различные должности. Все 12 кандидатов имеют равные шансы на занятие той или иной должности. Сколько существует всевозможных вариантов для выбора?

Решение. Используем правило умножения. Первого человека нужно выбрать из 12 кандидатов, следовательно, существует 12 способов выбора, второго человека выбирают из оставшихся 11, поэтому для осуществления второго действия имеется 11 способов. И, наконец, третьего человека выбираем из оставшихся десяти. Очевидно, что число способов осуществления третьего действия равно 10. По правилу умножения можно составить 12·11·10=1320 различных вариантов по 3 человека в каждом.

С другой стороны, число всевозможных вариантов выбора равно числу размещений из 12 человек по три. Очевидно, что комбинации, состоящие из трех человек, будут размещениями, так как они будут отличаться либо самими людьми, либо расположением этих людей соответственно их должностям (по условию примера – должности разные). Таким образом, число размещений из 12 человек по 3 равно 12·11·10=1320.■

Теорема 1.1. Число размещений из n элементов по т вычисляется по следующей формуле

(1.1)

где .

Доказательство. Для доказательства воспользуемся правилом умножения. Чтобы составить какое-либо размещение нужно выбрать т элементов из n элементов, при этом учитывать порядок выбора. Это означает, что нужно заполнить т мест элементами рассматриваемого множества следующим образом. На первое место может быть поставлен любой из n элементов, т.е. существует n способов выполнить первое действие. После этого останется n−1 элемент, каждый из которых может быть помещен на второе место, т.е. второе действие может быть совершено n−1 способами. Рассуждая аналогично, получим, что занятие третьего места может быть совершено n−2 способами, четвертого – n−3 способами и т.д. Последнее т-ое место может быть занято n−(т−1) способами. Таким образом,

.

Теорема доказана.

В теореме 1.1. для обозначения числа размещений используется буква А. Это связано с первой буквой французского слова «arrangement», что означает «размещение, приведение в порядок».

Формула (1.1) может быть преобразована к более удобному виду.

Теорема 1.2. Число размещений из n элементов по т может быть вычислено по следующей формуле

(1.2)

Доказательство. Для доказательства умножим и разделим правую часть формулы (1.1) на выражение (n−т)!. Оно не равно нулю, так как при т= n получаем 0!=1. Получим

Теорема доказана.

Пример 1.5. Сколько можно записать трехзначных чисел, используя без повторения все девять (кроме нуля) цифр?

Решение. Необходимо составить различные размещения из девяти цифр по три и найти их число. Итак,

.

Таким образом, можно составить 504 различные числа. ■

Изменим условие примера 1.5., и предположим, что при составлении чисел цифры могут повторяться, например, будем считать, что возможны числа 121, 144, 555 и т.д. Понятно, что в этом случае количество различных чисел будет значительно больше. Новые полученные комбинации чисел будут называться размещениями с повторениями.

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

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

Теорема 1.3. Число размещений с повторениями из n элементов по т вычисляется по следующей формуле:

(1.3)

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

Теорема доказана.

Пример 1.6. Сколько можно записать трехзначных чисел, используя все девять (кроме нуля) цифр? Цифры могут повторяться.

Решение. Число размещений с повторениями из девяти цифр по три равно

.

Таким образом, можно составить 729 различных чисел. ■

Рассмотрим пример 1.4. с дополнительным условием.

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

Решение. Как и в примере 1.4. речь идет о размещениях. Однако в этом случае допускается занятие одним человеком нескольких должностей, поэтому здесь используются размещения с повторениями. Таким образом,

,

т.е. существует 1728 вариантов выбора. ■

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