Симметричная расстановка ладей на доске [Комбинаторика]

[Whitaker]

Здравствуйте уважаемые!
В книге Виленкина "Комбинаторика" есть цикл параграфов, касающиеся расстановки фигур на шахматной доске.
Рассмотрим следующую задачу: нужно расставить ладьи симметрично относительно диагонали доски (для определенности берём диагональ, проходящую через нижнее левое угловое поле) и чтобы они не били друг друга. Обозначим через $Q_n$ решение данной задачи, когда $n$ ладей стоят на доске размера $n$x$n$.
В книге доказывается следующее соотношение: $Q_n=Q_{n-1}+(n-1)Q_{n-2}$. Но оказывается, что величина $Q_n=1+C_{n}^{2}+\dfrac{1}{1\cdot 2}C_{n}^{2}C_{n-2}^{2}+\dfrac{1}{1\cdot 2 \cdot 3}C_{n}^{2}C_{n-2}^{2}C_{n-4}^{2}+....$.
Написано, что эта формула выводится путем разбиения всех расположений ладей на классы - в $s$-й класс попадают расположения, при которых $s$ пар ладей не попадают на диагональ.

Но я пробую доказать последнюю формулу разбив на классы, но к сожалению не получается. Помогите пожалуйста как нужно получить формулу.

[Хорхе]

Если ровно пара ладей не попадает на диагональ, сколько будет таких расположений?

[Whitaker]

Хорхе в сообщении #495141 писал(а):

Если ровно пара ладей не попадает на диагональ, сколько будет таких расположений?

$n-2$ ладей на диагонали можно поставить $C_{n}^{2}$ способами, а оставшуюся пару ладей уже 1 способом. В итоге, получим $C_{n}^{2}$ способов.
А вот уже для других случаев не получается.

[Хорхе]

Да все получается, надо просто подумать. Задача облегчается тем, что ответ-то уже есть, вот он.

[Whitaker]

А если сделать так?
Так у нас доска размера $n$x$n$. Выбираем первую пару симметричных ладей, потом вторую пару симметричных из оставшихся,..., $s$-ю пару симметричных из оставшихся. И так как порядок выбора не важен, то делим на $P_s=s!$ и получим:
$\dfrac{1}{s!}C_{n}^{2}C_{n-2}^{2}C_{n-4}^{2}...C_{n-2(s-1)}^{2}$
Звучит наверное глупо, но этот,метод который Я написал не совсем понял

[Хорхе]

Вы все правильно написали. Осталось только понять

(Оффтоп)

Со мной тоже очень часто бывает, что не понимаю то, что написал. Если к этому привыкнуть, что ничего страшного.

На самом деле, это задача о числе инволюций -- перестановок, которые в квадрате равны себе. Можно в этом направлении подумать.

[Whitaker]

Хорхе кажется я понял.
Благодарю Вас за помощь!

С уважением, Whitaker.

[Хорхе]

(Оффтоп)

Whitaker, это Вы аватарку от радости поменяли? Ну вообще надо научиться не бояться (не) понимать вещи.

[Whitaker]

Хорхе можно и так сказать