Сколько зигзагов на шахматной доске?

[Xenia1996]

Зигзаг - это 8 белых клеток, по одной на каждой горизонтали, соприкасающиеся своими углами.
Например, b8-c7-b6-a5-b4-c3-d2-c1 - это зигзаг.
А сколько всего зигзагов на шахматной доске?

А если доска $n\times n$?
(при нечётном числе клеток доски красим клетки по правилу лайтонрайт, а зигзаг, естественно, не 8, а n клеток)

[Equinoxe]

Первый вопрос — 296, а в каком виде требуется ответ? В смысле, с большой вероятностью ответ представим в виде определенной матрицы, возведенной в степень n, а его численное значение — сумма чисел в получившейся матрице

[Xenia1996]

Equinoxe в сообщении #443075 писал(а):

Первый вопрос — 296, а в каком виде требуется ответ?

Ваш ответ для доски $8\times 8$ - верный.
Обобщение задачи на доску $n\times n$ - комбинаторная задача не из простых.

[Equinoxe]

А что нужно в итоге? Алгоритм? Формула?

[Xenia1996]

Equinoxe в сообщении #443080 писал(а):

А что нужно в итоге? Алгоритм? Формула?

Ну, если сможете формулу, Медаль Филдса Вам обеспечена (если Вам, конечно, нет сорока).

[Equinoxe]

Алгоритм элементарный, берем матричку n на n, первую строку заполняем единицами в местах, которым соответствует белая клетка, все остальное — 0. Остальное заполняем построчно: если клеточка соответствует белой, ставим сумму той, что слева сверху и справа сверху, иначе 0.

А формула у меня будет через матрицу, возведенную в степень, если будет конечно

[Xenia1996]

Equinoxe в сообщении #443089 писал(а):

Алгоритм элементарный, берем матричку n на n, первую строку заполняем единицами в местах, которым соответствует белая клетка, все остальное — 0. Остальное заполняем построчно: если клеточка соответствует белой, ставим сумму той, что слева сверху и справа сверху, иначе 0.

А формула у меня будет через матрицу, возведенную в степень, если будет конечно

Вот я 296 похожим алгоритмом нашла.
А попробуйте заменить 8 на 100. Не устанете считать?

[Equinoxe]

Xenia1996, ну, вся эта сумма очень похожа на C из n по k, тем не менее, C из n по k тоже требует вычисления факториала или всей таблички… К тому же, для 100 ответ будет порядка $2^{100}$…

[Xenia1996]

Equinoxe в сообщении #443101 писал(а):

Xenia1996, ну, вся эта сумма очень похожа на C из n по k, тем не менее, C из n по k тоже требует вычисления факториала или всей таблички… К тому же, для 100 ответ будет порядка $2^{100}$…

Я тут кое-что нашла по теме. Только вот не знаю - сейчас постить, или немного погодя. Ладно, дам людям ещё порешать.