Элементы комбинаторики

Пусть имеется различных объектов произвольной природы (множество объектов). Выберем из них объектов. Полученное подмножество называется выборкой.

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

Если объект А можно выбрать различными способами, а объект В – различными способами, то пару объектов А и В именно в таком порядке можно выбрать различными способами (правило умножения).

Если объект А можно выбрать различными способами, а объект В – различными способами, то выбрать один объект А или В можно различными способами (правило сложения).

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

Число всех возможных размещений по правилу умножения равно:

. (1.1)

Пример 1. Сколькими способами можно выбрать старосту и профорга из группы в 10 человек?

Решение. При выборе двух человек на должности старосты и профорга имеет значение порядок, в котором это делается. Значит, искомое число – это число размещений из 10 элементов по 2 элемента:

Перестановки – это размещения из n элементов по n элементов. Их количество равно:

. (1.2)

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

Решение. Десять книг образуют множество из n = 10 различных элементов, так как книги разные. Расположение книг на полке – это упорядочивание книг слева направо. Таким образом, расположение книг на полке – перестановка из 10-ти элементов. Поэтому число различных расположений 10-ти книг на полке совпадает с числом различных перестановок из 10-ти элементов и находится по формуле:

Пусть имеются k групп элементов, причем в первой группе неразличимых элементов, во второй группе неразличимых элементов, …, в k- ой группе – неразличимых элементов. Элементы из разных групп различимы. Таким образом, имеем всего элементов .

В этом случае имеют место перестановки с повторениями. Их число равно: . (1.3)

Пример 3. На шести карточках написаны буквы, из которых можно составить слово АНАНАС. Сколько существует различных шестибуквенных слов, которые можно составить при помощи этих 6-ти карточек?

Решение. 6 карточек разобьем на 3 группы. Первая группа образована карточками с буквой А. Число таких карточек равно 3. Они неразличимы по буквам, на всех одна и та же буква А. Вторая группа образована двумя карточками, содержащими букву Н. Элементы второй группы также неразличимы между собой. Третья группа образована одной карточкой с буквой С. Таким образом, мы имеем дело с перестановками с повторениями и число слов из 6-ти букв равно:

Число размещений с повторениями из элементов по элементов равно:

. (1.4)

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

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

(1.5)

Пример 4. В урне находятся 10 белых, 15 черных, 20 красных шаров. Из урны наудачу берут 9 шаров. Найдите:

1) Сколькими различными способами это можно сделать?

2) Сколькими различными способами можно взять 9 шаров, среди которых 6 белых и 3 черных?

Решение. 1) Всего в урне 45 шаров. Считаем, что шары различимы, например, пронумерованы. Следовательно, имеем множество из n = 45 различных объектов. Наудачу взятые 9 шаров образуют подмножество из k = 9 элементов. Это подмножество определяется лишь элементами, попавшими в него, порядок не имеет значения. Следовательно, это сочетание из 45 элементов по 9:

2) Взятые 9-ти шаров, из которых 6 белых и 3 черных, можно разбить на два действия: 1-е действие – возьмем 6 белых шаров из 10 белых шаров, находящихся в урне (это можно сделать различными способами); 2-е действие – возьмем 3 черных шара из общего числа 15 черных шаров (это можно сделать различными способами). Тогда число различных способов взятия 9-ти шаров нужного состава по правилу умножения равно: