Так вот, в Khan Academy есть раздел головоломок, очень занятный. Я не придумал сам, как решить togglers, а решение синих лбов до сих пор не готов принять. А вот тут результат посчитал правильно,
http://www.khanacademy.org/video/path-counting-brain-teaser - но у меня схема была куда менее элегантная (и уж тем более я не использовал факториалы, как надо было)
Варианта пойти со старта два, поэтому количество путей в прямоугольнике X на Y равно числу путей в прямоугольнике (X-1) на Y плюс числу путей в прямоугольнике (Y-1) на X.
Если одна сторона два, то можно не редуцировать, число вариантов равно второй стороне (то есть, сколько вариантов сдвинуться - по одному на каждую из клеток).
Соответственно, f(6x6)=2*f(5x6)
f(5x6)=f(5x5)+f(4x6)
=2f(5x4)+f(3x6)+f(4x5)
=3f(5x4)+f(3x6)
=3f(4x4)+3f(5x3)+f(2x6)+f(3x5)
=3f(4x4)+4f(3x5)+f(2x6)
=6f(4x3)+4f(3x4)+4*5+6
=10f(4x3)+26
=10f(4x2)+10f(3x3)+26
=40+20*3+26
=126
А у 6х6, соответственно, 252.
Ну только я не так расписывал, а нарисовал сначала мелкие квадратики и число путей в них посчитал, а потом пошел в сторону увеличения.
Но как это все объединить в упрощенную формулу - это еще надо подумать (как отсюда прийти к факториалу?)
