同じものを含む円順列の求め方

質問

はじめまして。

黒１・赤２・青２の玉を円周上に等間隔に並べるときの並べ方は
黒を固定して、残り赤２青２を直線上に並べた並べ方に等しくなるので、4!/2!2!=6（通り）ですよね？

では、黒３・赤３・青３といったように、１つ区別して固定できるものがない場合はどのように求めればよいのでしょうか？

回答No.2

nag0720 · ベストアンサー

もし、黒２・赤３・青３の場合だったら、１つだけ区別して固定できるものがありませんが、
(8-1)!/(2!3!3!)=70通りになります。
これは、円周上に並べたあとに回転したとしても同じ並びにならないからです。

ではもっと簡単にして、黒２・赤２の場合は、
(4-1)!/(2!2!)　となりそうですが、
黒赤黒赤の並びは、1/2回転すれば同じ並びになるので、その分を考慮すれば、
(4-1)!/(2!2!)+1/2=2通り

黒２・赤２・青２の場合は、
黒赤青黒赤青と黒青赤黒青赤は、1/2回転すれば同じ並びになるので、
(6-1)!/(2!2!2!)+(1/2)*2=16通り

黒３・赤３の場合は、
黒赤黒赤黒赤は、1/3回転と2/3回転すれば同じ並びになるので、
(6-1)!/(3!3!)+(1/3)*2=4通り

黒３・赤３・青３の場合は、
黒赤青黒赤青黒赤青と黒青赤黒青赤黒青赤は、1/3回転と2/3回転すれば同じ並びになるので、
(9-1)!/(3!3!3!)+(1/3)*4=188通り

黒４・赤４の場合は、
黒赤黒赤黒赤黒赤は、1/4回転と2/4回転と3/4回転すれば同じ並びに、
黒黒赤赤黒黒赤赤は、1/2回転すれば同じ並びになるので、
(8-1)!/(4!4!)+(1/4)*3+1/2=10通り

では、黒４・赤４・青４の場合はどうなるかどうなるでしょうか？

回答No.3

nag0720

＃２です。

もう少し考察してみます。

黒a個・赤b個・青c個の場合、

a,b,cの最大公約数が1の場合、円順列の数は、
(a+b+c-1)!/(a!b!c!)
となります。

a,b,cの最大公約数pが素数の場合は、
a'=a/p、b'=b/p、c'=b/p とおけば、円順列の数は、
(a+b+c-1)!/(a!b!c!)+(1-1/p)(a'+b'+c'-1)!/(a'!b'!c'!)
となります。

a=b=c=3の場合は、
p=3、a'=b'=c'=1　を代入すれば、
(a+b+c-1)!/(a!b!c!)+(1-1/p)(a'+b'+c'-1)!/(a'!b'!c'!)=188

黒赤青の３種類で考えましたが、それ以上の場合でも同じです。

問題となるのは、最大公約数が合成数の場合で、これはかなりやっかいですが、
最大公約数が２つの素数の積になる場合なら、がんばればなんとか式を導きだせるでしょう。

回答No.1

R_Earl

とりあえず思いついた方法を書いてみます。

円順列の場合の数の計算方法の考え方として、
「まず直線に並べる場合の数を考え、重複するものを取り除く」
という考え方があります。
例えばA, B, C, Dの4つを円形に並べる場合、まず直線に並べる並べ方が4!通りあります。
その4!通りの中には、例えば
ABCD
DABC
CDAB
BCDA
のような並びがあります。ABCDの並びと、その並びを1個ずつずらしたような並びです。
これらの4つの並べ方は円形にすると全く同じものになります。
他の並べ方でも同様の事が言えます。
例えばACBDという並びに対しては
ACBD
DACB
BDAC
CBDA
の4つの並べ方が、円形にすると全く同じ円順列になるものとなります。
つまり直線状に並べた時の順列の4つの並べ方のグループが、
1つの円順列になることになります。
なので4!通りの並び方を円形にすると、4!/4通りの円順列が作れる事になります。

なのでn個の異なるものを円形に並べる時は、
(n個の物を直線状に並べる並べ方) / n
で計算できる事になります。

これと同じ方法で、例えば白玉2つと黒玉2つを円形に並べる事を考えます。
白玉2つ、黒玉2つを直線状に並べる方法は4C2 = 6通りとなります。
これを列挙すると

○○●●
○●●○
●●○○
●○○●
○●○●
●○●○

となります。

ここで「周期性のある並び」と「周期性のない並び」に注目します。
例えば一番下の並べ方は「●○」の並べ方が連続しているので、
周期性のある並びとなります。

周期性のない並び(上4つの並べ方)に関しては先ほどと同じように、
並べるものの個数分の並べ方(つまり4通りの並べ方)が、円形にすると1つにまとまります。
しかし周期性のある並び(下2つの並べ方)に関してはそれが成り立ちません。
この例の場合、2通りの並べ方が円形にすると1つまとまります。
なのでこの場合、2通りの円しか作れません。

同じように黒3・赤3・青3の玉を円形に並べる場合を考えます。
この3つの玉を直線状に並べる方法は9C3×6C3 = 1680通りです。
このうち周期性のある並びは、周期3の

青黒赤青黒赤青黒赤
赤青黒赤青黒赤青黒
黒赤青黒赤青黒赤青

青赤黒青赤黒青赤黒
黒青赤黒青赤黒青赤
赤黒青赤黒青赤黒青

の並べ方6通りです。
よって周期性が無い並べ方は1674通りとなります。

周期性が無い並べ方は、9通りの並べ方が、円形にすると1つにまとまります。
よってこの周期性の無い並べ方を円形にすると、
(1674/9) = 186通りの円が作れます。

周期3の並べ方に関しては、3通りの並べ方が、円形にすると1つにまとまります。
よってこれを円形に並べると
(6/3) = 2通りの円が作れます。

よって186 + 2 = 188通りの円が作れるという事になります。

もしかしたらもっと簡単な解き方があるかもしれません。