Некоторые свойства и возможности применения объектов

Рекуррентные соотношения для сочетаний:

.

Сочетания и бином Ньютона. Формула для бинома имеет вид

. (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 (в ящики раскладываются не все предметы), вполне допустим.