Ладейный полином

[damir_777]

Здравствуйте.
В задачах на подсчет количества перестановок с некоторыми запрещенными позициями, часто удобно применять технику вычисления с помощью ладейного полинома. Для этого нужно на доске , допустим, квадратной, закрасить запретные позиции, на которые нельзя ставить ладью, а потом сделать вычисления. У меня возникла проблема как раз не с вычислением, а с закраской для
следующей задачи:
Сколькими способами можно рассадить в ряд трёх англичан, трёх французов и трёх турок так, чтобы никакие три соотечественника не сидели рядом.
Получается будет доска, девять на девять, но не могу понять какие клетки нужно закрасить

[arseniiv]

Вы собираетесь поставить туда 9 ладей, чтобы получить, кто рассажен на каком месте? Тогда при таком использовании ладей по идее никакие клетки доски исключить нельзя. Ведь то, куда нельзя посадить например англичан, зависит от того, где сидят другие англичане, а в общем случае каждого отдельного можно сажать куда угодно.

Кстати «чтобы никакие три соотечественника не сидели рядом» означает, что они могут сидеть рядом по двое, или что и по двое тоже нельзя и с каждой стороны должен сидеть кто-то чужой?

[Yadryara]

damir_777 в сообщении #1517480 писал(а):

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

Тут постановку надо уточнить, да. Какие способы считаются различными?

Вы пробовали посчитать это количество? При определённой трактовке получается меньше 200 способов.

[damir_777]

ну вообще в задаче сказано что только по трое, значит по двое можно сидеть я думаю. Ответ 238 824 способа. Просто описывается способ решения с помощью формулы включени и исключений. Это из книги Виленкин Комбинаторика (2006 год), задачи к главе 5.
Я просто почему хотел попробовать через полином, потому что вообще этот способ охватывает обширный класс задач, т.е. как бы универсальный. Потому что, например, субфакториалы - своя формула. задача о рассадке за круглым столом где должны чередоваться мужчины и женщины - своя формула.