Задача по комбинаторике.

[ELIZAVETA1996]

помогите пожалуйста решить задачу ,объяснить первый шаг/ ход решения.
Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они не били друг друга? (ладья бьёт фигуру по горизонтали и по вертикали). Указание. Зафиксировать положение первой ладьи и рассматривать комбинации для оставшихся.

Смогла рассчитать лишь количество способов для размещения первой ладьи, 2-ой , 3 ...8-0й :
1-64
2-49
3-36
4-25
5-16
6-9
7-4
8-1

помогите продвинуться в решении...

[Hasek]

Но ведь Вы уже всё посчитали... Теперь осталось только перемножить: $8^2 \cdot 7^2 \cdot 6^2 \cdot 5^2 \cdot 4^2 \cdot 3^2 \cdot 2^2 \cdot 1^2 = 1 625 702 400$ способов.

[Yadryara]

В таких задачах варианты, которые можно получить поворотами доски, отражениями и пр. обычно считают одинаковыми. Уточните, пожалуйста. В этом случае количество расстановок уже первой ладьи намного меньше $64$.

[kp9r4d]

А почему $k^2$? Скажем, если доска была бы 2 на 2, то неужто вариантов было бы $2^2$?

-- 27.02.2017, 10:24 --

А, понял логику. Но если так рассуждать, то мы посчитаем количество способов расставить разноцветные ладьи. А чтобы их сделать одноцветными нужно поделить на понятно что.

[Yadryara]

Для квадратной доски $n$-го порядка есть $C_{\lfloor{\frac{n+3}2}\rfloor}^2$ различных способов поставить одну ладью...

[Someone]

ELIZAVETA1996 в сообщении #1195667 писал(а):

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

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

[ELIZAVETA1996]

Someone

Насколько я поняла как раз условия стандартны - все ладьи одинаковые, а вертеть доску нельзя.

-- 28.02.2017, 11:00 --

Hasek
спасибо большое, я тоже пришла к такому ответу (8!)^2=1625702400

[Yadryara]

ELIZAVETA1996 в сообщении #1195914 писал(а):

спасибо большое, я тоже пришла к такому ответу (8!)^2=1625702400

Неужто этот ответ верен? Даже если не вертеть доску. Посмотрите на доски 2-го и 3-го порядков. Неужто для них правильные ответы $(2!)^2$ и $(3!)^2$ ??

[Hasek]

ELIZAVETA1996 в сообщении #1195914 писал(а):

я тоже пришла к такому ответу (8!)^2=1625702400

Извините, тут видимо моя вина, я написал то сообщение не особо вдумавшись в задачу. Таким вот образом мы посчитали число всех возможных расстановок с учётом порядка, как мы ставим фигуры на доску, (то есть не считаем их эквивалентными). Если понимать задачу более жизненно, конечно, все ладьи одинаковые и равноправные, поэтому нет разницы, в каком порядке их расставлять на доске, а значит, правильный ответ будет меньше, мы посчитали много лишнего. Понимаете, как его подкорректировать?

[ArtemKim]

http://www.kotesovec.cz/books/kotesovec ... 13_6ed.pdf
страница 216

[ELIZAVETA1996]

Hasek
если мы учитываем , что ладьи эквивалентные, тогда ответ будет просто 8!, верно?

[Someone]

Верно. Этот результат сразу получается, если расставлять ладьи не как попало, а по вертикалям (первую ладью — в первую вертикаль, вторую — во вторую…; или по горизонталям).

[Yadryara]

Да, верно и скучновато. А вот если учитывать по-настоящему различные расстановки, то их ещё гораздо меньше и посчитать количество существенно труднее.

Неплохо об этом рассказано в книге Соломона Вольфа Голомба "Полимино". Различные варианты этой задачи рассматриваются в главе "Подсчет разнородных объектов".

Ну и в OEIS, конечно же, всё есть. Полагаю, пруф уже можно: A000903.

[ELIZAVETA1996]

Всем большое спасибо, за помощь в решении!