円の並び方（全ての人が両隣が違うように並び替える）

並び替えの問題で、一般的な教科書に載っているような問題ではなく、ウェブ上で検索しても同じ質問を見つけることが出来なかったので、自分で質問することにしました。
お知恵をお貸しください。

■□■□■
10人が部屋に集まって、中央の円卓に、ランダムに座ったとします。
そして、今両隣にいる2人のうちどちらとも隣に来ないように並び替えます。
（つまり、両隣には全く新しい2人が来ます）

これを繰り返していったとして、何通りの並び方が出来ますか。
※部屋に入って最初にランダムに座った並びも1通りと数えてください。

■□■□■
私が取り組んでいる活動で、時々こういった活動をするんですが、参加者の人数に応じて、果たして何回入れ替えが出来るのだろうということが気になって質問させて頂きました。

※今回は10人としていますが、人数が変わってもすぐ計算できるように、単純な円順列や数珠順列のような公式的なものを教えて頂けると助かります。

No.3 回答者： Ku-Mei 回答日時： 2017/02/02 17:31

No.2 です。

前の回答のときに書き忘れたことがありますので、追加です。この問題は、大学の情報系（理工系でも？）の学科で学ぶ離散数学の中のグラフ理論の応用問題です。

グラフ理論で、n 点の完全グラフというグラフと、グラフのハミルトンサイクルとを学びます。これらの言葉を使って、問題を言い換えると、n 点の完全グラフに、辺を共有しないハミルトングラフの個数を求めよ、という問題になります。

No.2 回答者： Ku-Mei 回答日時： 2017/02/02 17:06

今は、１０人の問題ですが、一般的な形で、n 人の場合を考えます。

n 人を区別するために、その人たちに０から n - 1 までの番号を振ります。みんなが手をつないで輪になることを考えます。そのとき、適当な規則（後で述べます）で次に繋ぐ人を決めていき、うまくn 人で１つの輪ができるかどうかを調べます。できたらば、その規則でOKということになります。うまく n 人の輪ができる規則がいくつあるかを調べれば、この問題が解けることになります。
輪になっていることから、最初の人を 0 番の人としても一般性は失いませんから、そのようにします。
規則は、何人かが手を繋いでいるとき、次に手を繋ぐ人を決める方法で表すことにします（最後に、０番の人が決まると、輪が完成となります）。

規則ｋ：　i 番目の人まで決まっているとき、次に手を繋ぐ人は、i + k 番目の人とする。ただし、i + k が n 以上になったら、n で割った余り番目の人とする。

ためしに、規則１を使ってみると、
0, 1, 2, ..., n - 2, n -1, 0
という n 人の輪ができます。
規則２を使ってみると、n が偶数ならば、
0, 2, 4, ..., n - 1, 1, 3, 5, ..., n - 2, 0
となり、n 人の輪ができますが、奇数ならば、
0, 2, 4, ..., n -2, 0
となって、n 人の輪ができません。
この場合、２で n 割り切れるかどうかによって、n 人の輪ができるかどうかが決まることがわかります。
このことを一般化して、n が k(1 ではない）で割り切れないとき、n の輪ができることがわかります（割り切れるとき、輪ができないこともわかります）。
すると、問題は輪ができる規則がいくつあるかを数えればよいことになります。つまり、n が k で割り切れないような k がいくつあるかを調べればよいことになります。
ここで、注意しなければならないことがあります。たとえば、規則１と規則(n - 1) 都を考えてみると、お互いに逆回りになっていることが分かります（規則１は、次の人と右手で繋ぐことを表しているとすれば、規則(n - 1) は、左手で繋ぐことを表していることになるという関係です）。
このことを踏まえて、n を割り切らない k を探す範囲は、n/2 まででよいことが分かります。
したがって、求める数は、n を割り切らない n/2 以下の ｋ の個数プラス 1(規則１の分) となります。

折角ですから、No.1 さんの結果を参考に、試してみると、
n = 3 のとき、１通り
n = 4 のとき、１通り
n = 5 のとき、２通り (k = 1, 2)
n = 6 のとき、１通り (No. 1 さんの答えをどう読めばよいのかよく分かりませんでした。）
後は、ありませんでしたので、７から先の場合を書いておきます。
n = 7 のとき、３通り (k = 1, 2, 3) (k = 4 は、k = 3 と同じなど)
n = 8 のとき、2通り (k = 1, 3)
n = 9 のとき、３通り (k = 1, 2, 4)
n = 10 のとき、２通り ( k = 1, 3)
となります。

一般の n のときも、この考えで良いことが分かると思います。
改めて書いておきます。

n 人の人が円卓に着くとき、すべての人について両隣の人が異なるように着くことのできる席の着き方の数は、n/2 以下の n を割り切らない数の個数に１を加えた数である。

No.1 回答者： yuji3690 回答日時： 2017/02/01 02:28

とりあえず順番に考えてみます。

自分の位置に関わらず隣の人のみで判断するので、Aさんの位置を固定してみます。
規則性を見つけるには一応少ない人数から順番に考えてみましょう。
3人までは1通りですね。

4人
A-B-C-D-A　隣になってない人がそれぞれ1人しかいないので動けません。
なので1通りですね。

5人
A-B-C-D-E-A　それぞれ2人ずつ隣になっていない人がいます。
A-C-E-B-D-A　もしくはこの左右逆のパターン
となり2通りですね。

※毎回左右逆のパターンと付けるのは面倒なので省略します。

6人
A-B-C-D-E-F-A　それぞれ3人ずつ隣になっていない人がいます。
Aさんの隣にいけるのはCDEさん。
Dさんが隣に来ない場合
　Dさんの隣に来れるのはABFさんですが、BFさんの隣にAさんは来れないので、
　A-?-B-D-F-?-A　の形になります。よって
　A-C-F-D-B-E-A　だけですね。
Cさんが隣に来ない場合
　Cさんの隣に来れるのはAEFさんですが、BFさんの隣にAさんは来れないので、
　Cさんが中央の場合
　A-？-E-C-F-?-A　の形になってしまい、Bさんの行ける場所が無いので
　Cさんが中央ではない場合
　A-?-C-?-?-?-A　なので
　A-E-C-?-?-D-A　の形。つまり
　A-E-C-F-B-D-A　のみですね。
Eさんが隣に来ない場合
　Cさんの場合と同様です。
　A-?-B-E-C-?-A　ではFさんの行き場がありません
　A-?-E-?-?-?-A　なら
　A-C-E-?-?-D-A　となり
　A-C-E-B-F-D-A　のみですね。
3通りありますが、それぞれ次隣になれる人が１りしかいないので、
どのパターンでも席替えは1回（席のパターンだと2通り）しかできません。

7人…とする必要もないですね。分かりましたか？
1度席替えをすると、どんなに上手くやっても隣になれる人は2人減ります。
（下手な並び替えをすると、もっと減ります）
つまり、最初の人数が10人であれば、最初座った時点で席替えして隣になれる人は残り7人、2回目で5人、3回目で3人、4回目で1人となり、5回目の席替えは不可能です。
よって５通りの並びができますね。
N人の場合だと、(N+1)/2通りですね。（少数以下切捨て）