1.4.3. Сочетания
Если из всех размещений, которые можно составить из n элементов по m, отобрать только те, которые отличаются друг от друга, по крайней мере, одним элементом, то получим соединения, которые называются сочетаниями. Например, из трех элементов a, b, c сочетания по 2 будут:
ab, ac, bc
Если в каждом из этих сочетаний сделаем все возможные перестановки, то получим все возможные размещения из трех элементов по 2. Это справедливо и в общем случае произвольных n и m.
Таким образом,
число всех размещений из n
элементов по m равно числу всех
сочетаний из n по m,
умноженному на число перестановок
,
какие можно сделать в каждом сочетании
по m элементов, то есть
,
где
означает число всех сочетаний из n
элементов по m.
Отсюда выводим следующую формулу для числа сочетаний:
.
Умножая числитель
и знаменатель правой части этой формулы
на
,
который равен
,
получим
.
Следовательно, формулу для числа сочетаний можно записать и так:
,
откуда легко
увидеть следующее важное свойство
симметрии
.
Это равенство имеет четкий смысл для m < n .
В комбинаторике
удобно принимать, что указанное свойство
симметрии справедливо и для m
= n, то есть
.
Учитывая, что
,
для согласованности приведенных выше
формул полагают, по определению, что
и
.
Числа
часто
называют еще биномиальными
коэффициентами и обозначают так
.
Таким образом,
,
,
.
Такое название
этих чисел связано с тем, что они являются
коэффициентами разложения n-ой
степени бинома
по
степеням
:
,
это частный случай общей формулы, называемой кратко бином Ньютона.
1.4.4. Задачи о размещении элементов по ячейкам.
В абстрактной формулировке это – задача о числе вариантов размещения m шаров по n ящикам.
Многие схемы комбинаторики, внешне весьма различные, по существу эквивалентны абстрактной схеме распределения m шаров по n ящикам.
Так распределение дней рождения m человек соответствует размещению m шаров по n =365 ящикам (см. выше, пример 1.2.3). Классификация m несчастных случаев по дням недели, в которые они происходят (см. там же пример 1.2.4), эквивалентна размещению m шаров по n =7 ящикам. Заметим, что часто употребляемый в этой ситуации термин “размещение”, используется как синоним термина “распределение”. Последний более предпочтителен в нашем контексте, поскольку он не вносит путаницу с понятием размещения как вид соединений.
Обращаясь к задачам качества, рассмотрим партию из N изделий, в которой D изделий являются дефектными. Все изделия находятся в ячейках по одному в каждой ячейке. Сколько возможно вариантов размещения D дефектных изделий по N ячейкам? Ячейки предполагаются перенумерованными, а изделия различаются только по признаку годности. Очевидно, что интересующее нас число размещений совпадает с числом возможных выборов D мест из заданных N для размещений дефектных изделий. Порядок этих мест роли не играет, так как все дефектные изделия в известном смысле равноправны.
Следовательно, искомое число вариантов совпадает с числом сочетаний из N по D, то есть равно
.
Можно разрешить помещать в ячейку любое число (не больше D) дефектных изделий. Тогда число возможных размещений определяется формулой
.