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

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

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

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

.

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

2!= 1·2=2

3!= 1·2·3=6

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

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

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

Размещения

Выберем из трех элементов 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 способов выполнить первое действие. После этого останется n1 элемент, каждый из которых может быть помещен на второе место, т.е. второе действие может быть совершено n1 способами. Рассуждая аналогично, получим, что занятие третьего места может быть совершено n2 способами, четвертого – n3 способами и т.д. Последнее т-ое место может быть занято 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 вариантов выбора.

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

Перестановки

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

a b с, b a с, b c а, c b а, a c b, c a b.

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

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

Иначе, перестановки – это размещения из n элементов по n. Нетрудно получить формулу для числа перестановок.

Теорема 1.4.Число перестановок из n различных элементов равно

(1.4)

Доказательство. Используем то, что перестановки – частный случай размещений. По формуле (1.2) получим

.

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

В теореме 1.4. для обозначения числа перестановок использовалась буква Р, что соответствует начальной букве французского слова «permutation», в переводе – перестановка.

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

Решение. Каждый день все 5 изданий должны быть просмотрены, может меняться лишь порядок просмотра, поэтому число способов просмотра равно .

Пример 1.9. На полке стоят 7 учебников, 3 из которых по эконометрике. Сколько существует способов расстановки семи различных книг на полке так, чтобы 3 учебника по эконометрике стояли рядом?

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

Во всех рассмотренных ранее примерах предполагалось, что элементы в одной перестановке все различны. Если допустить наличие одинаковых элементов в перестановке, то получим перестановки с повторениями. Так как перестановки – это частный случай размещений, то учитывая формулу (1.3) можно получить следующую формулу для числа перестановок с повторениями

(1.5)

Пример 1.10. Сколько различных чисел можно составить из трех цифр 3, 4, 5?

Решение. Применяя формулу (1.5), получим . Решим эту же задачу другим способом, без применения формулы (1.5).

Числа, состоящие из трех предложенных цифр можно разделить на три группы. В первую группу входят числа, в которых все цифры разные, например, 345, 534 и т.д. Очевидно, что их число равно 3!=6. Вторая группа состоит из чисел, в которых имеется две одинаковых цифры, например, с двумя цифрами 3 существует 6 различных чисел: 334, 343, 433, 335, 353, 533. Аналогично существует по 6 различных чисел с двумя цифрами 4 и 5. Следовательно, вторая группа состоит из 18 чисел. Наконец, третья группа составлена из чисел, в которых все три цифры одинаковы, т.е. 333, 444, 555. Таким образом, общее количество чисел равно 6+18+3=27.

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

Пусть среди n элементов есть n₁ элементов одного вида, n₂ элементов второго вида и т.д. и n_k элементов k-го вида, тогда число перестановок из этих чисел равно

(1.6)

где n₁+ n₂+…+ n_k= n.

Пример 1.11. Сколько существует различных шестизначных чисел, в которых цифра 1 повторяется два раза, цифра 3 один раз, цифра 5 – три раза?

Решение. Из условия задачи ясно, что n=6, n₁=2, n₂=1, n₃=3. По формуле (1.6) получим .

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

Сочетания

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

a b, b c, a c.

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

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

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

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

(1.7)

где .

Доказательство. Выведем эту формулу, используя формулы для числа размещений (1.2) и числа перестановок (1.4). Нетрудно понять, что если сначала составить различные сочетания из n элементов по т, а потом в каждом из сочетаний различными способами поменять порядок, т.е. произвести перестановки, то получим различные размещения из n элементов по т. Следовательно, по правилу умножения имеет место формула . Отсюда получаем .

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

Буква С в обозначении числа сочетаний взята от начальной буквы слова «combination», что в переводе означает сочетание.

Числа называются биномиальными коэффициентами, так как они входят в разложение формулы бинома Ньютона:

.

Числа обладают следующими свойствами:

1) ;

2) ;

3) , где т=0, 1, …, n, удобно применять при ;

4) , где т=0, 1, …, n1.

Пример 1.12. Решить пример 1.4., предполагая, что кандидаты выбираются на одинаковые должности.

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

.

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

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

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

(1.8)

Необходимо обратить внимание на то, что в формуле (1.8) число т может быть и больше n. Например, число способов выбора 6 авторучек, если в продаже имеется 4 вида авторучек, может быть определено по формуле:

.

Очевидно, что в этом примере т=6, а n=4.