Комбинации

Пример 1 Найдите все комбинации 3-х букв, взятых из набора в 5 букв {A, B, C, D, E}.

РешениеЭти комбинации следующие:
{A, B, C},          {A, B, D},
{A, B, E},          {A, C, D},
{A, C, E},          {A, D, E},
{B, C, D},          {B, C, E},
{B, D, E},          {C, D, E}.
Существует 10 комбинаций из трех букв, выбранных из пяти букв.

Когда мы находим все комбинации из набора с 5 объектами, если мы берем 3 объекта за один раз, мы находим все 3-элементные подмножества. В таком случае порядок объектов не рассматривается. Тогда,
{A, C, B} называется одним и тем же набором как и {A, B, C}.

Подмножество
Множество A есть подмножеством B, и означает что A это подмножество и/или совпадает с B если каждый элемент A является элементом B.

Элементы подмножество не упорядочены. Когда рассматриваются комбинации, не рассматривается порядок!

Комбинация
Комбинация, содержащая k объектов является подмножеством, состоящим из k объектов.

Мы хотим записать формулу для вычисления число сочетаний из n объектов, если взято к объектов одновременно.

Обозначения комбинации
Число сочетаний из n объектов, если взято к объектов одновременно, обозначается _nC_k.

Мы называем _nC_k число сочетаний. Мы хотим записать общую формулу для _nC_k для любого k ≤ n. Во-первых, это верно, что _nC_n = 1, потому что множество с n элементами имеет только одно подмножестов с n элементами, есть само множество. Во-вторых, _nC₁ = n, потому что множество с n элементами имеет только n подмножеств с 1 элементом в каждом. Наконец, _nC₀ = 1, потому что множество с n элементами имеет только одно подмножество с 0 элементами, то есть пустое множество ∅. Чтобы рассмотреть другие сочетания, давайте вернемся к примеру 1 и сравним число комбинаций с числом перестановок.

Обратите внимание, что каждая комбинация из 3-х элементов имеет 6, или 3!, перестановок.
3! • ₅C₃ = 60 = ₅P₃ = 5 • 4 • 3,
so
.
В общем, число сочетаний из k элементов, выбранных из n объектов , _nC_k раз перестановок этих элементов k!, должно быть равно числу перестановок n элементов по k элементов:
k!._nC_k = _nP_k
nC_k = _nP_k/k!
_nC_k = (1/k!)._nP_k
nC_k =

Комбинации k объектов из n объектов
Общее число комбинаций к элементов из n объектов обозначается _nC_k, определяется
(1)          _nC_k = ,
или
(2)          _nC_k =

Другой тип обозначения для _nC_k это биноминальный коэффициент . Причина для такой терминологии будет понятна ниже.

Биноминальный коэффициент

Пример 2 Вычислите , используя формулы (1) и (2).

Решение
a) Согласно (1),
.
b) Согласно (2),

Имейте в виду, что не означает n/k.

Пример 3 Вычислите и .

Решение Мы используем формулу (1) для первого выражения и формулу (2) для второго. Тогда
,
используя (1), и
,
испоьлзуя формулу (2).

Обратите внимание, что
,
и используя результат примера 2 дает нам
.
Отсюда вытекает, что число 5-ти элементного подмножества из множества 7 элементов то же самое, что и число 2-элементного подмножества множества из 7 элементов. Когда 5 элементов выбираются из набора, они не включают в себя 2 элемента. Чтобы увидеть это, рассмотрим множество {A, B, C, D, E, F, G}:

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

Подмножества размера k и размера
и _nC_k = _nC_n-k
Число подмножеств размера к множества с n объектами такое же, как и число подмножеств размера n - к. Число сочетаний k объектов из множества n объектов, такое же как и число сочетаний из n объектов, взятых одновременно.

Теперь мы будем решать задачи с комбинациями.

Пример 4 Мичиганская лотерея. Проводящаяся в штате Мичиган два раза в неделю лотерея WINFALL имеет джек-пот, который, по крайней мере, равен 2 млн. долларов США. За один доллар игрок может зачеркнуть любые 6 чисел от 1 до 49. Если эти числа совпадают с теми, которые выпадают при проведении лотереи, игрок выигрывает. (Источник: Мичиганская лоттерея)
a) Сколько возможных комбинаций из 6-ти чисел в этой лотерее?
б) Предположим, что 10 минут у Вас идет на то, чтобы купить лотерейный билет и зачеркнуть 6 чисел. Сколько лотерейных билетов вы можете купить за 4 дня?
c) Сколько людей вы должны были бы нанять на 4 дня, чтобы купить билеты со всеми возможными комбинациями и быть уверенным, что вы выиграете?

Решение
a) Здесь нет порядка чисел. Вы зачеркиваете любые 6 чисел от 1 до 49. Тогда, число возможных комбинаций равно

b) Во первых, мы посчитаем число минут в 4 -х днях:
4days • (24 ч/1 день).(60 мин/1 ч) = 5760 мин.
Тогда, вы могли бы купить 576 билетов за 4 дня.
c) Вам необходимо было бы нанять 13,983,816/576, или около 24278 человек чтобы купить билеты со всеми возможными комбинациями для гарантированного выигрыша. (С условием, что билеты можно покупать 24 часа в сутки.)

Пример 5 Сколько комитетов может быть сформировано из группы 5-ти губернаторов и 7-ми сенаторов, если каждый комитет состоит из 3-х губернаторов и 4-х сенаторов?

Решение Три губернатора могут быть избраны ₅C₃ путями и 4 сенатора могут быть избраны ₇C₄ путями. Если мы используем фундаментальный метод подсчета, то получим, что число возможных комитетов равно