同じものを含む円順列 - 数学 @ ウィキ

同じものを含む円順列

概要

円順列とは、円形に配置するとき「回転して同じに見える並べ方を1つと数える」という考え方。

同じものを含む場合（例：AABB, AAABBBなど）は、や
のような単純な公式が使えなくなる。

理由：並べ方ごとに「回転して元に戻る周期」が変わるから。

---

周期とは？

並びを円上で回したとき、何回回すと元の見た目に戻るか、という値。
並びの長さを n とすると、周期は必ず n の約数になる。

例（n=6）：

• ABABAB → 周期2（ABの繰り返し）
• ABBBBA → 周期6（どの回転でも一致しない）
• ABBABA → 周期6
• AAAAAA → 周期1（全部同じ）

周期が揃わないため、公式は作れない。

---

基本の考え方

円順列の個数は次の手順で求める。

1. 0回転（そのまま）で一致する並べ方の数を数える
2. 1回転で一致する並べ方の数
3. 2回転で一致する並べ方の数
…
(n−1)回転まで調べる
4. それらをすべて合計し、 n で割る

これは「回して同じものを1つにまとめる」ための処理。

---

周期の簡単判定法

長さ n の並び S が周期 d を持つとは、Sをd個だけ右にずらしても同じ列になるということ。
dはnの約数だけになる。

• d=1 → 全部同じ
• d=2 → 2文字のパターンを3回繰り返す（例：ABABAB）
• d=3 → 3文字の並びを2回繰り返す（例：ABCABC）
• d=6 → 繰り返しなし

---

例題1：AABB を円に並べる

Step1：線形の順列

A2個、B2個なので
6通り。

並びの一覧：

A A B B
A B A B
A B B A
B A A B
B A B A
B B A A

Step2：各回転で一致するか調べる

周期候補は 1,2,4（n=4）

• 0回転（何もしない）：6通り
• 1回転：一致は0
• 2回転（180°回転）：一致する並びはAABB、BBAAの2通り
• 3回転：一致は0

Step3：平均を取る

答え：2通り

例題2：AAABBB を円に並べる

Step1：線形順列は

=20)

Step2：周期ごとに分類

周期候補は 1,2,3,6（n=6の約数）

• 周期1：不可能（全部同じでないため）
• 周期2：可能

 2文字を3回繰り返す形。  
 A3、B3 は 3 の倍数なので可。  
 → 2通り（ABABAB / BABABA）

• 周期3：不可能

 A3, B3 は 2の倍数ではないため

• 周期6：残り

 20 - 2 = 18 通り

Step3：回転ごとの一致数を数える

• 0回転：20
• 1回転：0
• 2回転：周期2 → 2
• 3回転：周期3 → 0
• 4回転：周期2 → 2
• 5回転：0

合計24

答え：4通り

---

発展：長さ n・A が k 個の一般公式

• ：オイラーの関数。正の整数nに対し、n以下の数でnと互いに素なものの個数を数える関数。
• 和はの約数 d について取る

---

まとめ

• 円順列では回して同じものを1つと数える
• 同じものを含むと並びごとに周期が変わる
• 周期＝繰り返し構造であり、n の約数のみ
• 結局、「周期ごとの並び数」を使えば計算できる
• AABB → 2通り
• AAABBB → 4通り
• n と A の個数を固定すれば一般公式も存在する