Открытая Математика. Алгебра. Сочетания

Сочетания

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

Всякая неупорядоченная выборка объёма k из множества, состоящего из n элементов, (k ≤ n) называется сочетанием из n элементов по k. Количество сочетаний обозначается $C_{n}^{k}$ и вычисляется по формуле $C_{n}^{k} = \frac{n!}{k! (n - k)!} .$

Символ $C_{n}^{k}$ читается «це из эн по ка».

Формулу для $C_{n}^{k}$ можно получить из следующих соображений.

Из любого набора, содержащего k элементов, можно получить k! перестановок. Поэтому упорядоченных выборок объёма k существует $A_{n}^{k} = C_{n}^{k} ċ P_{k}$ штук. Значит, $C_{n}^{k} = \frac{A_{n}^{k}}{k!} = \frac{n!}{k! (n - k)!} .$

Сочетания

Для проведения письменного экзамена нужно составить 3 варианта по 5 задач в каждом. Сколькими способами можно разбить 15 задач на 3 варианта?

Задачи первого варианта можно выбрать $C_{15}^{5}$ способами. После этого останется 10 задач, следовательно, второй вариант можно составить $C_{10}^{5}$ способами. Для третьего варианта задачи можно выбрать $C_{5}^{5} = 1$ способом. По правилу произведения получаем, что число способов равно $C_{15}^{5} C_{10}^{5} .$ Однако нам всё равно, какой вариант будет первым, какой – вторым, а какой – третьим. Потому найденное число нужно разделить на число перестановок из трёх элементов, то есть на 3!. Окончательно получаем, что число способов равно $\frac{1}{3!} C_{15}^{5} C_{10}^{5} = \frac{1}{3!} ċ \frac{15!}{5! ċ 10!} ċ \frac{10!}{5! ċ 5!} = 126126$ способов.

Ответ. 126126.

Сколькими способами можно разместить 10 различных шаров по 4 ящикам так, чтобы в первом ящике оказалось 2 шара, во втором – 3, в третьем – 3 и в четвёртом снова два?

Пусть в первый ящик попадет $m_{1}$ шаров, во второй – $m_{2},$ в третий – $m_{3}$ шаров, а в четвёртый – $m_{4} .$ Тогда количество способов выборки в первый ящик $m_{1}$ из n шаров определяется числом $C_{n}^{m_{1}},$ количество способов выборки во второй ящик $m_{2}$ шаров из $(n - m_{1})$ оставшихся – числом $C_{n - m_{1}}^{m_{2}},$ для 4-го ящика – $C_{n - m_{1} - m_{2} - m_{3}}^{m_{4}},$ а для k-го ящика то же число будет равно $C_{n - m_{1} - ... - m_{k - 1}}^{m_{k}} .$ Ответ найдётся по правилу произведения: $C_{n}^{m_{1}, ..., m_{k}} = C_{n}^{m_{1}} C_{n - m_{1}}^{m_{2}} ... C_{n - m_{1} - ... - m_{k}}^{m_{k}} = \frac{n!}{m_{1}! ... m_{k}!} .$ В нашем случае $C_{n}^{m_{1}, ..., m_{4}} = \frac{n!}{m_{1}! ... m_{4}!} = \frac{10!}{2! 3! 3! 2!} = 25200 .$

Для числа сочетаний $C_{n}^{k}$ справедливы некоторые тождества, в частности:

$C_{n}^{n - k} = C_{n}^{k},$
$C_{n + 1}^{k} = C_{n}^{k} + C_{n}^{k - 1} .$

Докажите тождество $C_{n + 1}^{k + 1} = C_{n}^{k + 1} + C_{n}^{k} .$

С помощью формулы для $C_{n}^{k}$ получаем: $C_{n}^{k + 1} + C_{n}^{k} = \frac{n!}{(k + 1)! (n - k - 1)!} + \frac{n!}{k! (n - k)!} = \frac{n! ((n - k) + (k + 1))}{(k + 1)! (n - k)!} = \frac{(n + 1)!}{(k + 1)! (n - k)!} = C_{n + 1}^{k + 1} .$

Запишем в «нулевой» строке число $C_{0}^{0} = 1 .$ В первой строке напишем значения чисел $C_{1}^{0}$ и $C_{1}^{1},$ каждое из которых тоже равно 1, так, чтобы значение $C_{1}^{0}$ оказалось над промежутком между этими двумя числами. Во второй строке запишем числа $C_{2}^{0}$ и $C_{2}^{2},$ тоже равные 1, а между ними – число $C_{2}^{1} = 1 .$ Обратим внимание, что число $C_{2}^{1}$ равно сумме двух чисел, стоящих над ним: $C_{2}^{1} = C_{1}^{0} + C_{1}^{1} .$ Продолжим построение, записывая в n-й строке числа от $C_{n}^{0}$ до $C_{n}^{n}$ включительно.

Треугольник Паскаля

Полученный числовой треугольник называется треугольником Паскаля. Согласно свойству $C_{n + 1}^{k} = C_{n}^{k} + C_{n}^{k - 1},$ любое число в этом треугольнике равно сумме двух чисел, расположенных над ним в предыдущей строке.

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

Доказать, что $\sum_{k = 1}^{n} C_{n}^{k} = 2^{n} .$

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

Эти числа образуют геометрическую прогрессию со знаменателем 2: 1, 2, 4, 8, 16 и так далее. При этом сумма чисел в нулевой строке $C_{0}^{0} = 1 = 2^{0},$ в первой строке $C_{1}^{0} + C_{1}^{1} = 2 = 2^{1},$ во второй строке $C_{2}^{0} + C_{2}^{1} + C_{2}^{2} = 4 = 2^{2}$ и так далее. Строгое доказательство этого факта производится методом математической индукции.

Итак, $\sum_{k = 1}^{n} C_{n}^{k} = 2^{n} .$

На языке множеств утверждение, доказанное в задаче, выглядит по-другому.

Число подмножеств множества из n элементов равно 2ⁿ.

Еще один интересный факт, связанный с треугольником Паскаля, мы приведём здесь без доказательства:

{(a + b)}^{n} = C_{n}^{0} a^{n} + C_{n}^{1} a^{n - 1} b^{1} + ... + C_{n}^{n - 1} a^{1} b^{n - 1} + C_{n}^{n} b^{n} = \sum_{k = 0}^{n} C_{n}^{k} a^{n - k} b^{k} .

Приведённое тождество называется биномом Ньютона.

Как и в случае с размещениями, существует понятие числа сочетаний с повторениями. Рассмотрим его на следующем примере.

В палитре художника 8 различных красок. Художник берет кистью наугад любую из красок и ставит цветное пятно на ватмане. Затем берет следующую кисть, окунает её в любую из красок и делает второе пятно по соседству. Сколько различных комбинаций существует для шести пятен? Порядок пятен на ватмане не важен.

Решим задачу следующим образом. Пусть количество пятен первого цвета равно k₁, второго цвета – k₂, третьего – k₃ и так далее. Запишем каждое из этих чисел последовательностью из соответствующего количества единиц, а на границах между числами поставим нули. Так, если у нас первого цвета 1 пятно, второго – 3 пятна, третьего и четвёртого – ни одного, пятого и шестого – по одному пятну, а седьмого и восьмого – снова не одного, то запись будет выглядеть следующим образом: 1011100010100. В этой цепочке содержится m₁ = 6 единиц, m₀ – 1 = 8 – 1 = 7 нулей – всего n = m₀ + m₁ – 1 = 13 цифр. Количество перестановок с повторениями этих цифр равно $\frac{n!}{m_{1}! (m_{0} - 1)!} = \frac{13!}{6! 7!} = 1716 .$ Именно столько существует различных вариантов раскраски ватмана (без учёта порядка цветных пятен).

Вообще, можно сформулировать следующее правило.

Если из множества, содержащего n элементов, выбирается поочередно m элементов, причём выбранный элемент каждый раз возвращается обратно, то количество способов произвести неупорядоченную выборку – число сочетаний с повторениями – составляет ${\tilde{C}}_{n}^{m} = P_{m, n - 1} = \frac{(n + m - 1)!}{m! (n - 1)!} .$

Смотрите также: Математика, Английский язык, Химия, Биология, Физика, География, Астрономия.
А также: библиотека ЭОРов и образовательный онлайн-сервис с тысячами интерактивных работ "Облако знаний".

Учебник. Сочетания

ГЛАВНАЯ

НОВОСТИ

УЧЕБНИК

ДОСТУП К БЕСПЛАТНЫМ УРОКАМ