Question

Нужна помощь с задачей по комбинаторике.
На шахматном поле 8х8 стоит фигура левом верхнем углу и ей нужно попасть в правый нижний угол. За каждый шаг она может передвигаться либо на одно поле горизонтально вправо, либо на одно поле вниз. Сколько всего существует путей у фигуры?

Answer 1

Ну тут мы можем смело выдвинуть формулу. В клетке (x,y) число переходов к ней это сумма клеток (x-1,y)+(x,y-1). Теперь заметим неизменчивость одного. Каждый путь спускается вниз на 8 клеток. То есть у пути есть выбор из 2 путей - вниз или влево. Причем так встречается только 8 раз. Дальше - нет выбора. Заметим, что эти пути обхватывают всю доску. Раз 8 раз по 2 пути встречается, значит количество путей - $2^{8} = 256$