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

Будем пользоваться тем, что только что доказали в прошлом примере. Рассмотрим -е число из -й строки. Чтобы до него добраться, надо ровно раз пойти вниз-вправо, а остальные раз пойти вниз-влево. По сути надо из ходов выбрать те , на которых мы пойдем направо. Как мы уже знаем, количество способов выбрать из ходов без учета порядка равно , значит, и количество способов добраться до рассматриваемого числа равно . Но также мы уже знаем, что количество способов добраться до числа равно самому числу, значит, в строчке под номером на -м месте стоит число , что и требовалось доказать.