ラウンドテーブルには、人は何通​​りの異なる方法で着席できますか？

Question

私はアルゴリズムを開発しており、結論に至るまでに最大反復回数の可能性を検討しています。

現実の世界では、古典的な円卓座席の問題に似ています。あなたは繰り返して丸テーブルに着席する方法の最大数を教えていただけますか？

おかげ

Answer 1

この問題の解決方法をトレースしてみましょう。

まず、n人を1行に整列させる方法を見てみましょう。私たちがラインの前に置くことができるn人の異なる人がいます。残っているn - 1のうち、n - 1のいずれかを第2の位置に置くことができる。より一般的には、数式は次のようになります。

数字配列= nx（n-1）x（n-1） 2）x ... x 1 = n！

したがって、n！人をラインで並べ替えるさまざまな方法。より一般的には、n！ n個のユニークな要素を並べ替えるためのさまざまな方法。

ここで、人を指輪に配置するとどうなりますか？線形置換のそれぞれについて、2つの端部を接続することによってその配置をリング配列に変換することができる。たとえば、3人と、ラインでそれらを注文する6つの方法があります。

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

これらのマップは、次のリングへ：

  1 
1 2 3 ->/\ 
     3---2 

      1 
1 3 2 ->/\ 
     2---3 

      2 
2 1 3 ->/\ 
     3---1 

      2 
2 3 1 ->/\ 
     1---3 

      3 
3 1 2 ->/\ 
     2---1 

      3 
3 2 1 ->/\ 
     1---2 

しかし、我々がいることをこのことから結論することはできませんnの座席数の配列！私たちはここで同じ座席の配置を何度も作成しているからです。トリックとして、1がサイクルの最上位になるように常にサイクルを書き出すとしましょう。だから、実際には、2つだけ異なる配列がある

1    1 
/\ x3  /\ x3 
2---3   3---2 

;：私たちは次のように生成した

  1 
1 2 3 ->/\ 
     3---2 

      1 
1 3 2 ->/\ 
     2---3 

      1 
2 1 3 ->/\ 
     2---3 

      1 
2 3 1 ->/\ 
     3---2 

      1 
3 1 2 ->/\ 
     3---2 

      1 
3 2 1 ->/\ 
     2---3 

がお知らせ：その後、我々は次のサイクルを生成しました私たちはそれらのそれぞれを3回生成しました。

この理由は、リングには明確な開始点と終了点がないため、異なる配置のそれぞれを複数回回転させることになります。特に、座っておく必要がある人がn人いると、同じ回転のn個の異なるコピーが生成されます.1つは異なるゲストのそれぞれが先頭に表示されます。したがって、ゲストの総数を取得するには、それぞれのリングごとに、それらのうちの1つを除くすべてを無視する必要があります。各リングのn個の異なるコピーが存在するので、これは総数がによって与えられることを意味する

n！/n =（n-1）！

だから、（n - 1）！リングに人を置くためのさまざまな方法。

希望すると便利です。

Answer 2

クラシック順列の問題：二つの部分にそれを破る：彼らは重要ではありませんので、開始位置の数（としてn）で 1）すべての可能な組み合わせ 2）分割

I get（n-1）！可能性。ここに何もないのですか？ （私は多くの統計をしないので、私はちょっと錆びている）