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




Сочетания

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

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

Символ C n k читается «це из эн по ка».

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

Из любого набора, содержащего k элементов, можно получить k! перестановок. Поэтому упорядоченных выборок объёма k существует A n k = C n k ċ P k штук. Значит, C n k = A n k k! = 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!. Окончательно получаем, что число способов равно 1 3! C 15 5 C 10 5 = 1 3! ċ 15! 5!ċ10! ċ 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 = n! m 1 !... m k ! . В нашем случае C n m 1 , ...,  m 4 = n! m 1 !... m 4 ! = 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 = n! (k+1)!(n-k-1)! + n! k!(n-k)! = n!((n-k)+(k+1)) (k+1)!(n-k)! = (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 , любое число в этом треугольнике равно сумме двух чисел, расположенных над ним в предыдущей строке.

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

Доказать, что 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 и так далее. Строгое доказательство этого факта производится методом математической индукции.

Итак, k=1 n C n k = 2 n .

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

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

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

( 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 = k=0 n C n k a n-k b k .

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

 

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

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

Решим задачу следующим образом. Пусть количество пятен первого цвета равно k1, второго цвета – k2, третьего – k3 и так далее. Запишем каждое из этих чисел последовательностью из соответствующего количества единиц, а на границах между числами поставим нули. Так, если у нас первого цвета 1 пятно, второго – 3 пятна, третьего и четвёртого – ни одного, пятого и шестого – по одному пятну, а седьмого и восьмого – снова не одного, то запись будет выглядеть следующим образом: 1011100010100. В этой цепочке содержится m1 = 6 единиц, m0 – 1 = 8 – 1 = 7 нулей – всего n = m0 + m1 – 1 = 13 цифр. Количество перестановок с повторениями этих цифр равно n! m 1 ! ( m 0 -1 ) ! = 13! 6! 7! =1716 . Именно столько существует различных вариантов раскраски ватмана (без учёта порядка цветных пятен).

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

Если из множества, содержащего n элементов, выбирается поочередно m элементов, причём выбранный элемент каждый раз возвращается обратно, то количество способов произвести неупорядоченную выборку – число сочетаний с повторениями – составляет C ˜ n m = P m, n-1 = ( n+m-1 ) ! m!( n-1 ) ! .





 

© Физикон, 1999-2015