Задача о супружеских парах

[Whitaker]

Здравствуйте уважаемые друзья!
В книжке М. Холла "Комбинаторика" наткнулся на известную задачу "Задача о супружеских парах", но не могу понять один момент в ходе решения. Помогите пожалуйста.
Хозяйка желает рассадить $n$ супружеских пар за круглым столом так, чтобы мужчины и женщины чередовались, но чтобы при этом ни один муж не сидел рядом со своей женой.
Рассадим сначала на местах через одно женщин, обозначая их номерами $1, 2, \cdots, n$ по кругу. обозначим место слева от $i$-й женщины и справа от $(i+1)$-й женщины номером $i$ и номером $n$ -место между $n$-й женщиной и первой. Тогда первый муж может сесть на любое место, кроме $n$-го и первого, а $i$-й муж - на любое место кроме $(i-1)$-го и $i$-го.
Если муж с номером $a_i$ сидит на месте $i$, то $a_1a_2\dots a_n$ есть перестановка чисел $1, 2, \cdots, n$ и наше условие означает, что перестановка $a_1a_2\cdots a_n$ должна удовлетворять условию: $a_i\neq i, i+1$ при $1\leq i \leq n-1$ и $a_n\neq 1, n$.
Объясните пожалуйста почему $a_1\neq 1, 2$? Ведь должно быть $a_1\neq 1, n$ (так как первый муж не может сидеть на $n$-м и первом местах).

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

[alcoholist]

(Оффтоп)

Вы, главное, людям не мешайте... они так и рассядутся: М-Ж... и никто со своей второй половиной рядом не сядет

[Whitaker]

А если серьезно?

[Whitaker]

Ответьте пожалуйста на мой вопрос

[svv]

... 3 3 2 2 1 1 n n ...
Это несколько последовательных мест за столом.

(Thank you, Mr.Hall)

Marshall Hall писал(а):

обозначим место слева от $i$-й женщины и справа от $(i+1)$-й женщины номером $i$ и номером $n$ -место между $n$-й женщиной и первой.

Спасибо, мистер Холл, именно это требование заставило меня написать список "наоборот".

Розовым обозначено место, где сидит женщина. Розовое число -- это и номер места, и номер женщины.
Синим обозначено место, где сидит мужчина. Синее число -- это только номер места, но не номер мужчины.

Marshall Hall писал(а):

Тогда первый муж может сесть на любое место, кроме $n$-го и первого.

Верно, как раз места n и 1 находятся рядом с 1.

Marshall Hall & Whitaker писал(а):

Если муж с номером $a_i$ сидит на месте $i$, то $a_1a_2\dots a_n$ есть перестановка чисел $1, 2, \cdots, n$ и наше условие означает, что перестановка $a_1a_2\cdots a_n$ должна удовлетворять условию: $a_i\neq i, i+1$ при $1\leq i \leq n-1$ и $a_n\neq 1, n$.
Объясните пожалуйста почему $a_1\neq 1, 2$? Ведь должно быть $a_1\neq 1, n$ (так как первый муж не может сидеть на $n$-м и первом местах).

Потому что в записи перестановки $a_i$ -- это не "на какое место сел i-й муж", а "какой муж сел на i-е место".
Перестановка $312$ означает
"на первом месте муж 3, на втором месте муж 1, на третьем месте муж 2", а не
"первый муж на месте 3, второй муж на месте 1, третий муж на месте 2"

Теперь взгляните ещё раз:
... 3 3 2 2 1 1 n n ...
"Чему может быть равно $a_1$?" означает "какой муж может сидеть на 1?
Так как 1 находится между 1 и 2, это место может занять любой муж, кроме 1 и 2.

[Whitaker]

Могу рассказать о том, что я конкретно еще не понял. Непонятно, к чему обозначение $P(i): a_i = i, i + 1$. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как $n$ может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.
Если кому-нибудь не трудно объясните пожалуйста.