円周上の n個のコイン、全ての表裏パターンの一般式

質問

円周上に配置した n個のコインには表裏があり、その全ての表裏パターンを
導出する一般式を作りたいのですが、その規則性の着眼点はどの部分でしょうか。

回転すれば同じになる表裏パターンは全て同一とみなします。
ちなみに私が計算したら、n = 8の場合は 36パターン、
n = 10の場合は 108パターン、n = 11の場合は 188パターンでした。

回答No.3

kanemoto_s · ベストアンサー

＞複雑で驚きました。
公式は回転可能と素因数分解の関係が端的に記述された式になってますね。

http://www.nexyzbb.ne.jp/~hataeins/math/math.pdf
の公式IIから白の数をp,黒の数をqとして、(a,b)はaとbの最大公約数、
1/n(Σ[k=1,n ただし p(n,k)/n q(n,k)/n が自然数の時] (n,k)! / {(p(n,k)/n)! (q(n,k)/n)!})

n=8なら、代入して
1/8(Σ[k=1,8 ただし p(8,k)/8 と q(8,k)/8 が自然数の時] (8,k)! / {(p(8,k)/8)! (q(8,k)/8)!})
p=0,q=8　→　1 (計算不能だが)
●●●●●●●●
p=1,q=7　→　k=8のみ (1/8)( 8! / 1!7! ) = 1
○●●●●●●●
p=2,q=6　→　k=4,8 (1/8)( 4! / 1! 3! + 8! / 2! 6!) = 4
○●●●○●●● ○○●●●●●● ○●○●●●●● ○●●○●●●●
p=3,q=5　→　k=8のみ (1/8)( 8! / 3! 5! ) = 7
○○○●●●●● ○○●○●●●● ○○●●○●●● ○○●●●○●● ○○●●●●○● ○●○●○●●● ○●○●●○●●
p=4,q=4　→　k=2,4,6,8 (1/8)( 2! / 1! 1! + 4! / 2! 2! + 2! / 1! 1! +8! / 4! 4!) = 10
○●○●○●○●
○○●○○●●● ○○●○●○●● ○○●●○●○● ○○●●●○○● ○○●○●●○●
○○○●○●●● ○○○●●○●● ○○○●●●○●
○○○○●●●●
p=5,q=3　→　7　（対称なので計算は以下省略）
p=6,q=2　→　4
p=7,q=1　→　1
p=8,q=0　→　1
上記の全てを足すと合計36通り

＞n = 18個なら何パターン？
計算間違えがなければ、
p q 小計
0 18 1
1 17 1
2 16 9
3 15 46
4 14 172
5 13 476
6 12 1038
7 11 1768
8 10 2438
9 9 2704
10 8 2438
11 7 1768
12 6 1038
13 5 476
14 4 172
15 3 46
16 2 9
17 1 1
18 0 1
全14602通りだと思います。

↓計算したエクセルファイル
http://kanemoto.mydns.jp/~shuuji/chishiki/q9100708.zip
では、お休みなさい
;つД｀)

お礼

早速の回答を頂きありがとうございます。　他の掲示板で同じ質問を
しても、こんなに早く回答はもらえないのですが、
さすがにOkwebは早くて的確だと思いました。

n = 18個の場合は14602通りにもなるのですか。
これを手計算でやるなら完全にお手上げですが、エクセルで計算が
できるんですね。　これも勉強になりました。　（＾人＾）感謝♪

回答No.2

kanemoto_s

#1です。
失礼、予想は大外れでした、(>_<)

ネットで「同じものを含む円順列の一般化」を調べれば書いてありましたね。
http://www.nexyzbb.ne.jp/~hataeins/math/math.pdf

補足

早速の回答を頂きありがとうございます。　質問者であるmk4243は、
円周上に配置した n個のコインの、全ての表裏パターンの一般式は、
単なる表裏パターンだから、n = で始まる割りと簡単な一般式だろうと

思っていましたが、提示して頂いたURLを見るとかなり複雑で驚きました。
この説明文書でも、数種類の色が指定された場合での、円周配置での計算
が示されていますが、

質問の、全ての表裏パターンは n個であれば、表n個-裏0個から始まって
表0個-裏n個までの計算ですから、この説明文書のどの式が一番適合する
でしょうか。　そして例えば n = 18個なら何パターンになりますか。

お忙しいとは思いますが、時間に余裕のある時にでも回答頂けると
ありがたいです。

回答No.1

kanemoto_s

同じものを含む円順列の問題ですよね。

コインの総数を素因数分解して同じものができない組み合わせを考える必要が出てくると思います。
素数の問題が絡むので一般化できなくて、コンピューターで調べるしかないと予想するのですが。
大学入試程度の知識しかないので、スマートな解法があるかもしれません。