Математика

Тема 20.

Сочетания.

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

К примеру, имеются пять гвоздик разного цвета. Обозначим их буквами a,b,c,d,e. Требуется составить букет из трёх гвоздик. Выясним, какие букеты могут быть составлены.

Если в букет входит гвоздика a, то можно составить такие букеты:

abc, abd, abe, acd, ace, ade.

Если в букет не входит гвоздика а, но входит гвоздика b, то можно получить такие букеты:

bcd, bce, bde.

Если в букет не входит ни гвоздика а, ни гвоздика b, то возможен только один вариант составления букета:

сde.

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

Число сочетаний из n элементов по k, обозначают (читается «С из n по k»).

В рассмотренном примере, составив все сочетания из 5 элементов по 3, мы нашли, что

${С}_5^3=10$

Выведем формулу числа сочетаний из n элементов по k, где k≤n.

Выясним сначала, как ${С}_5^3$ выражается через ${А}_5^3$ и Р₃. Мы нашли, что из 5 элементов можно составить следующие сочетания по 3 элемента:

abc, abd, abe, acd, ace, ade, bcd, bce, bde, сde.

В каждом сочетании выполним все перестановки. Число перестановок из 3 элементов равно Р₃. В результате получим все возможные комбинации из 5 элементов по 3, которые различаются либо самими элементами, либо порядком элементов, т. е. все размещения из 5 элементов по 3. Всего мы получим размещений.

Значит,

${С}_5^3\bullet {Р}_3={А}_5^3$

Отсюда, ${С}_5^3=\frac{{А}_5^3}{{Р}_3}$

Аналогично будем рассуждать в общем случае. Допустим, что имеется множество, содержащее n элементов, и из его элементов составлены все возможные сочетания по k элементов. Число таких сочетаний равно ${С}_n^k$. В каждом сочетании можно выполнить Р_k перестановок. В результате мы получим все размещения, которые можно составить из n элементов по k. Их число равно ${А}_n^k$. Значит, $A_n^k=C_n^k\bullet P_k$

Отсюда, ${С}_n^k=\frac{{А}_n^k}{{Р}_k}$, пользуясь тем, что ${А}_n^k=\frac{n!}{\left(n-k\right)!}$, где $k\le n$, находим, что

${С}_n^k=\frac{n!}{k!\left(n-k\right)!}$.

Мы получили формулу для вычисления числа сочетаний из n элементов по k при любом $k\le n$.

Рассмотрим примеры:

Задача 1. Сколько различных стартовых шестерок можно образовать из числа 10 волейболистов?

Решение:

Так как при игре в волейбол функции игроков практически равны, то значение имеет только состав шестерки. Тогда

Ответ: 210 стартовых шестерок.

В шахматном кружке занимаются 2 девочки и 7 мальчиков. Для участия в соревновании необходимо составить команду из четырёх человек, в которую обязательно должна входить хотя бы одна девочка. Сколькими способами это можно сделать?

В команду входит либо одна девочка, либо две. Разберём оба случая. Если в команде две девочки, то двух мальчиков к ним можно добавить ${С}_7^2$ способами. Если же в команду входит только одна девочка (её можно выбрать двумя способами), то команду можно дополнить тремя мальчиками ${С}_7^3$ различными способами. Таким образом, общее число возможных команд равно.

${С}_7^2+2{С}_7^3=91$