пути ладьи

[oveka]

Сколькими вариантами ладья может перейти за 6 ходов с угла обычной шахматной
доски в противоположный угол?

[kiyanyn]

oveka в сообщении #515393 писал(а):

Сколькими вариантами ладья может перейти за 6 ходов с угла обычной шахматной
доски в противоположный угол?

Надо понимать, что ладья может двигаться только, скажем, вправо и вверх? Не возвращаясь? и чередуя направления ходов? (т.е. не допускается, например, a1-h1-h2-h3-h4-h5-h8)

При этих ограничениях, как мне кажется, надо 7 единичных ходов разбить на 3 участка; если верить Кнуту :), это делается $C_{7-1}^{3-1}=15$ способами, да умножить на столько же способов во втором направлении. Ну и, поскольку можно ходить сначала по горизонтали, а потом по вертикали, и наоборот - надо удвоить способы, т.е. вроде бы всего $2\cdot15\cdot15=450$ способов?...

[oveka]

Где посмотреть этого Батога (Кнута)? Спасибо.

[kiyanyn]

oveka в сообщении #515404 писал(а):

Где посмотреть этого Батога (Кнута)? Спасибо.

Ну, в английском варианте том 4 есть кое-где на торрентах...

Но в данном случае я приплел Кнута не более чем для пущей важности :) Смотрите - крайние точки при ходах в одном направлении известны. Остается 6 клеток, из которых надо выбрать две для "переломов" ломаной. Понятно, что число способов их выбрать - это просто число сочетаний из 6 клеток по 2 переломные... Все не просто просто, а очень просто

[Shadow]

А если без ограничений (каких в условии и нет) то 116192.

[oveka]

Shadow в сообщении #515624 писал(а):

А если без ограничений (каких в условии и нет) то 116192.

А как собирать эти варианты?

[Shadow]

Можно разделить полей доски на на 3 зоны и вычислить вероятность попадания ладьи через n ходов в соответную зону. В рамках зоны все поля уже равновероятны. В первой зоне - толко одно поле - начальное A1. Во второй - горизонталь 1 и верикаль A (исключая A1) - 14 полей. В третьей - все остальные -49. Если обозначить вероятности попадания соответствено $p,q,r$, можно получить рекурентную формулу:

$\\p_1=0, q_1=1, r_1=0\\ p_k=\frac{1}{14}q_{k-1}\\ q_k=p_{k-1}+\frac{3}{7}q_{k-1}+\frac{1}{7}r_{k-1}\\ r_k=1-p_k-q_k$

И число способов будет $\dfrac{14^6r_6}{49}$

Можно рассмотреть отдельно ходов по горизонтали и вертикали (так легче будет всего 2 зоны и вероятности легко вычисляются - сумма геом. прогресии) и посчитать комбинации попадания на 8-е поле. Результат такой же. А, возможно, существует метод и получше.

[oveka]

Спасибо, Shаdow, за науку.

[Shadow]

Второй вариант все таки лучше (первый для компютера) и без вероятностей. Число способов попасть на точно определенное неначальное (восьмое) поле через к "горизонтальных" ходов
$a_1=1, a_2=6, a_3=43, a_4=300, a_5=2101$. Т.е. $a_n=7^{n-1}-a_{n-1}$ С учетом $k$ горизонтальных и $6-k$ вертикальных, число способов

$\sum\limits_{k=1}^{5}C_6^ka_ka_{6-k}$