3.2. Некоторые свойства и возможности применения объектов
Рекуррентные соотношения для сочетаний:
.
Сочетания и бином Ньютона. Формула для бинома имеет вид
. ( 3.9 )
Следствия из формулы ( 3.9 ):
а) если X = 1, Y = 1, то
; ( 3.10 )
б) eсли X = -1, Y = 1, то
. ( 3.11 )
Отношения между объектами. Связь комбинаторных объектов:
, , ( 3.12 )
. ( 3.13 )
Во второй главе (пример 2.5) рассматривалась задача о числе подмножеств n-элементного множества, и для ее решения был применен принцип взаимно однозначного соответствия. В примере 3.6 предлагается другой способ решения, основанный на использовании формулы для числа сочетаний и равенства (3.10).
К числу сочетаний можно сводится также комбинаторная ситуация примера 2.1 (движение из пункта А в пункт С). Данная ситуация рассматривается в примере 3.7.
Широко примененяется в различных комбинаторных задачах формула (3.13). Это, в частности, относится к задачам, решение которых может быть сведено к раскладыванию предметов по ящикам (урнам, коробкам), т.е. к решению следующей комбинаторной задачи:
Пусть имеются n различных предметов и k ящиков. Предметы раскладываются по ящикам, причем в первый ящик кладется m предметов, во второй - l предметов, ... , в k-й - s предметов. Требуется найти число способов (вариантов) разложения (распределения) предметов по ящикам, если m + l + ... + s = n .
Рассмотрим два подхода к решению сформулированной задачи, которые, с одной стороны, по-разному интерпретируют процесс раскладывания предметов по ящикам и, с другой стороны, подтверждают правомерность использования перестановок и сочетаний, входящих в левую и правую части формулы (3.13):
1. Разложим, придерживаясь условий задачи, предметы по ящикам и будем считать, что предметы, попавшие в i-й ( i = 1,2,...,k ) ящик, относятся к предметам i-го типа, т.е. являются однотипными.
Так как перекладывание предметов внутри любого ящика не меняет варианта распределения предметов по ящикам, то получение любого другого конкретного варианта сводится к составлению некоторой перестановки (с повторениями) n предметов k различных типов. При этом, очевидно, каждому варианту разложения соответствует единственная (уникальная) перестановка и, наоборот, каждой перестановке - единственный вариант разложения.
Следовательно, искомое число вариантов совпадает с количеством перестановок с повторениями, т.е. с левой частью равенства ( 3.13 ).
2. Будем постепенно (последовательно, поэтапно) заполнять ящики нужным числом предметов:
на первом (начальном) этапе выберем произвольным образом m предметов и положим их в первый ящик; количество различных способов такого выбора равно, очевидно, числу сочетаний из n предметов по m, т.е. ;
на следующем (втором) этапе выберем по схеме случайного выбора l предметов из оставшихся (n-m) и положим их во второй ящик; по аналогии количество способов такого выбора будет совпадать с ;
заполняя по очереди имеющиеся ящики, перед последним k-м этапом будем иметь s нераспределенных (оставшихся) предметов; так как именно это число предметов должно быть в последнем ящике, то его заполнение можно осуществить единственным способом, что соответствует числу сочетаний = 1 (см. пример 3.8).
Учитывая тот факт, что количество способов выбора на каждом шаге не зависит от количества способов выбора на других шагах, искомое число вариантов распределения предметов по ящикам можно записать в виде произведения, стоящего в правой части равенства (3.13).
Замечание. На первый взгляд равенство m + l + ... + s = n, отражающее тот факт, что все имеющиеся n предметов должны быть обязательно разложены по всем k ящикам, является серьезным ограничением. На самом деле это не так.
В действительности, сводя конкретную комбинаторную задачу к раскладыванию предметов по ящикам, мы сами выбираем, сколько взять ящиков и сколько предметов положить в каждый из них.
Этот выбор должен удовлетворять определенным требованиям. В частности, нельзя делать выбор таким образом, чтобы после него имело место неравенство m + l + ... + s > n, так как в этом случае задача не будет иметь решения. В то же время мы вполне можем выбрать на один ящик меньше, чем требуется для раскладки всех предметов, так как закладка предметов в последний ящик - чисто формальное действие.
Данное утверждение подтверждается тем, что последний множитель в правой части выражения (3.13), соответствующий этому действию, всегда равен единице, т.е. он не меняет общего числа способов и может быть исключен (его присутствие в выражении носит чисто формальный характер). Таким образом, случай, когда имеет место неравенство m + l + ... + s < n (в ящики раскладываются не все предметы), вполне допустим.