Поток комбинаторики

Вы, возможно, и не заметили, но когда вы отвечали на вопросы из предыдущего раздела, вы углубились в область математики, из-

вестную под названием комбинаторика. Как вы могли догадаться по вашим ответам на эти вопросы, комбинаторика концентрируется на задачах о подсчитывании объектов или наборов объектов, обычно очень точном и систематичном. Вычисление индексов Банцафа часто включает в себя подсчет числа различных способов, которыми можно выбрать некоторое множество объектов. Например, в пункте (б) воп- роса 7.15 нам нужно было подсчитать число различных способов, которыми можно было выбрать трех из пяти представителей в фе- деральной системе Психозии. Если немного поразмыслить, то легко увидеть, что существует ровно десять способов сделать это.

Но что если ситуация усложняется? Например, что если нам нуж- но подсчитать число способов, которыми можно выбрать 51 из юо се- наторов в федеральной системе США? Именно на вопросы такого ти- па нам помогают отвечать методы комбинаторики. Давайте начнем с обозначений.

Определение 7.19. Число различных способов выбрать к объек- тов из множества п объектов обозначается , читается как «число сочетаний из п по к».

Вопрос 7.20*. Найдите значение каждой из следующих величин. (Заметьте. Хотя, вы, возможно, помните формулу для (J^j из преды- дущего курса, вам не обязательно использовать ее для ответа на этот вопрос; достаточно лишь подумать, что представляет собой каждая из этих величин.)

W® «О W© ^(г)(з)

«© «© ^(ж)®⁺(5) «О

Если вы внимательно посмотрите на ваши ответы на вопрос 7.20, вы заметите несколько полезных свойств. Например, должно быть

справедливо равенство (^j = 1, поскольку есть только один способ

выбрать нуль объектов из множества пяти объектов. (Этот способ состоит в том, чтобы из пяти объектов не выбирать ничего.) Но те же самые рассуждения применимы, если мы рассматриваем множество из шести, восьми или юо объектов. Итак,

Теорема 7.21. ГЧ = i для любого значения п.

Какой простой ни казалась бы эта теорема, она представляет со- бой один из полезных фактов, которые помогут нам найти Qj для

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

Вопрос 7.22*. Какое соотношение есть между и (_п^_^)?

Приведите убедительные доводы, чтобы объяснить, почему это соот- ношение справедливо для любых возможных значений пик. (Под- сказка. Может быть, вам будет полезно вернуться к вашим ответам на вопрос 7.20.)

Вопрос 7-23*- Заполните пропуски таким образом, чтобы каж- дое из следующих утверждений оказалось истинным. Затем приведи- те убедительные доводы, чтобы объяснить, почему каждое утвержде- ние справедливо в общем случае. (Подсказка. Возможно, вначале вам захочется рассмотреть некоторые примеры, особенно для пункта (в).)

(а) = для любого значения п.

(б) = для любого значения п.

(в) ^ ^_ ^ + = ⁺ Для любых значений пик.

Теперь давайте сопоставим все эти факты. При этом мы позна- комимся с известной математической конструкцией, известной как треугольник Паскаля, он назван в честь Блеза Паскаля, математи- ка XVII века. В треугольник Паскаля входят различные значения

упорядоченные в виде треугольника. Его первые четыре ряда

изображены на рисунке 7.1. Треугольник распространяется вниз до

Влиятельность Шепли—Шубика в Психозии

145