4.2.3. Сочетания

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

Формулу для

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

Из любого набора, содержащего k элементов, можно получить k! перестановок. Поэтому упорядоченных выборок объёма k существует

штук. Значит,

Пример 1

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

Показать решение

Пример 2

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

Показать решение

Для числа сочетаний

справедливы некоторые тождества, в частности:

Запишем в «нулевой» строке число

В первой строке напишем значения чисел

каждое из которых тоже равно 1, так, чтобы значение

оказалось над промежутком между этими двумя числами. Во второй строке запишем числа

тоже равные 1, а между ними – число

Обратим внимание, что число

равно сумме двух чисел, стоящих над ним:

Продолжим построение, записывая в n-й строке числа от

до

включительно.

Полученный числовой треугольник называется треугольником Паскаля. Согласно свойству

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

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

Пример 4

Доказать, что

Показать решение

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

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

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

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

Пример 5

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

Показать решение

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


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


	Если из множества, содержащего n элементов, выбирается поочередно m элементов, причём выбранный элемент каждый раз возвращается обратно, то количество способов произвести неупорядоченную выборку – число сочетаний с повторениями – составляет

Глава 4. Комбинаторика

4.2. document.write('Комбинаторика');

4.2.3. document.write('Сочетания'); window.top.document.title = "4.2.3. Сочетания";

4.2.

4.2.3.