Свойства биноминальных коэффициентов. Треугольник Паскаля

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

1.

2.

3.

4. Если и , то .

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

a. Выбрать 0 (так же, как и все ) элементов из возможных можно только одним способом.

b. Выбрать элементов из – это все равно, что указать те элементов, которые мы не выбираем.

c. Любое сочетание из по является -элементным подмножеством -элементного множества. Число - это количество таких подмножеств. Сумма таких чисел по всем от 0 до дает (по правилу сложения) количество всех возможных подмножеств -элементного множества.

Теперь посчитаем это же количество по-другому. Любое подмножество -элементного множества можно закодировать двоичной (т.е. состоящей из 0 и 1) последовательностью длины : на -м месте стоит 1, если -й элемент входит в это подмножество, 0 – если не входит. А всего таких последовательностей (а значит и всех возможных подмножеств) по правилу умножения .

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

Последнее из доказанных свойств позволяет вычислять числа не по выведенной ранее формуле с факториалами, а рекуррентно, последовательно выражая числа с бóльшим значением через предыдущие: Шаг 1. Найдем Шаг 2. Найдем . Выразим через уже известные: Шаг 3. Найдем . Выразим через уже известные: , … и так далее. Процесс вычисления чисел удобно организовать в виде таблицы (еще одно применение таблиц!): будем заносить в -ю строку этой таблицы все числа . Поскольку в -ой строке будет таких чисел, то таблица получится «треугольной»: k N               …                                                                                                                               ...... Причем закономерность заполнения клеток в этой таблице очень простая: в первую клетку очередной строки ставим 1, а в каждую следующую – сумму чисел стоящих в предыдущей строке левее и над ним (например: 2 = 1 + 1); заканчиваем строку также 1. Полученная треугольная таблица получила название треугольник Паскаля, по имени великого французского математика Блеза Паскаля, изучавшего свойства этого треугольника и использовавшего его при решении вероятностных задач.

Если составить треугольник из кружков, как показано на рисунке слева, то общее число кружков в таком треугольнике будет (считаем, что в нем слоев): По этой причине числа , стоящие во втором столбце треугольника Паскаля, принято называть треугольными.