Числа сочетаний (цэ изэн пока)

Будем доказывать, что число способов попасть в каждое число равно самому этому числу. Сначала рассуждаем на примере числа 20.

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

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

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

Но с другой стороны, по правилу построения треугольника Паскаля, . Значит, количество способов попасть в число равно , что и требовалось доказать.