Элементарная комбинаторика и бином Ньютона

Правила подсчёта

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

Сосчитать элементы множества значит пронумеровать их: сопоставить каждому числу от $1$ до $n$ элемент, не повторяя ни одного и не пропуская ни одного. Говорят, что множество $A$ содержит $n$ элементов, где $n$ натуральное, если существует биекция множества $\{1, 2, \ldots, n\}$ на $A$, то есть функция, переводящая различные числа в различные элементы и достигающая всех элементов $A$; пустое множество содержит $0$ элементов, а множество конечно, если оно пусто или содержит $n$ элементов для некоторого натурального $n$. Биекции, их композиция и обратная к биекции функция изучаются в уроке о множествах, отношениях и функциях.

Факт, принимаемый без доказательства (число элементов). Без доказательства принимается, что число элементов конечного множества определено корректно: множество не может одновременно содержать $m$ элементов и $n$ элементов, если $m \neq n$. Принимается также, что всякое подмножество конечного множества конечно.

Оба факта доказываются индукцией по $n$; первый по существу есть принцип Дирихле, согласно которому не существует функции, переводящей $n + 1$ чисел из $\{1, \ldots, n + 1\}$ в различные числа из $\{1, \ldots, n\}$. Их доказательства длинны и не дают идей, которые используются дальше, и поэтому они принимаются. Без первого выражение «число элементов» не имело бы смысла, и комбинаторное доказательство, считающее одно и то же множество двумя способами, не могло бы заключить, что два результата равны.

Индукцией по числу частей правило распространяется на любое конечное число попарно непересекающихся множеств: объединение множеств $A_1, \ldots, A_r$, содержащих $n_1, \ldots, n_r$ элементов, содержит $n_1 + \cdots + n_r$ элементов, потому что объединение $r + 1$ первых множеств есть объединение $r$ первых с последним, которое не имеет с ними общих элементов. Из него выводится второе правило, которое считает выборы, совершаемые по этапам.

Точно так же индукцией по числу этапов правило произведения распространяется на любое конечное число этапов: выбор в $r$ этапов, которые можно совершить соответственно $n_1, n_2, \ldots, n_r$ способами, можно совершить $n_1 n_2 \cdots n_r$ способами. Например, в десятичной системе, изученной в уроке о позиционных системах счисления, существует $9 \cdot 10 \cdot 10 = 900$ трёхзначных чисел, потому что первая цифра не может быть равна $0$, а две другие свободны. Следует заметить, что правило произведения требует, чтобы число вариантов на каждом этапе не зависело от сделанного ранее выбора, хотя сами варианты могут от него зависеть; если это условие нарушено, разбирают случаи, в которых оно выполняется, и складывают их результаты по правилу суммы.

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