ｸｲｽﾞ大陸

ようやく正解者が現れました。めでたしめでたしです。
前回のヒントから日が経ちましたので、またヒントを出したいと思います。

赤石または白石の個数が0個のとき、首飾りの総数は1です。
赤石または白石の個数が1個のときも首飾りの総数は1です。
村長の発言「今年は去年の首飾りをばらして組み替えるだけでよい」から、
首飾りの総数は1ではないことが分かりますので、赤石、白石ともに2個以上です。

赤石と白石の合計個数をnとします。
個数の少ない方の石を礎石と呼ぶことにします。
同数のときはどちらでも好きな方とします。
礎石の個数をkとします。
このとき、首飾りの総数を計算する方法を考えてみます。

全操作は、回転n個と反転n個の2n個です。
各々の操作において変化しない配置の個数を調べます。
まずは回転について考えます。
0度の回転の場合、すべての配置が不変です。
1個隣にずらす回転の場合、すべての石が同じ色であればすべての配置が不変、
異なる色がある場合は、どのような配置も不変ではありません。
2個隣にずらす回転の場合、一つおきに並んだすべての石の色が同じである必要があります。
もちろん、nは2の倍数でなくてはいけません。

n個の回転を、1個ずらす回転からn個ずらす回転までのn個と考えます。
mを1以上n以下の自然数とし、m個ずらす回転に対する不変配置の個数を考えます。

mとnの最大公約数をgcd(m,n)、s=n/gcd(m,n)とします。
n/s=gcd(m,n)です。
n個の石を連続するn/s個の石のグループs個に分けたとき、
それぞれのグループ内の赤石、白石の配置がすべて等しいときに不変となります。
kもsで割り切れなくてはいけませんので、sはnとkの公約数です。
各グループの石の総数はn/s個、礎石の数はk/s個ですので、
グループ内の石の配置の総数はC(n/s,k/s)個です。
(C(n,k)=nCkです)
つまり、m個ずらす回転に対する不変配置の個数は、s=n/gcd(m,n)として、
C(n/s,k/s)個です。

nとkの公約数sに対してmとnの最大公約数がn/sになるようなmがいくつあるのか考えてみます。
mとnの最大公約数がn/sということは、
m÷(n/s)とn÷(n/s)が互いに素ということです。
t=m÷(n/s)=ms/nとすると、tとsが互いに素です。
0＜m≦nですので、0＜ms/n≦n×s/n=sであり、0＜t≦sです。
tの個数は、1以上s以下の自然数でsと互いに素なもののの個数、すなわちφ(s)個です。
(φはオイラーのトーティエント関数。詳しくは新マオークエスト第三幕参照)
tとmは一対一に対応しますので、mの個数も同じです。
よって、回転に対する不変配置の個数の総計は、
Σφ(s)C(n/s,k/s)
[sはn,kの公約数]
となります。

例えばn=12,k=6のとき、
12と6の公約数は1,2,3,6の４つですので、回転に対する不変配置の個数の総計は、
φ(1)C(12/1,6/1)+φ(2)C(12/2,6/2)+φ(3)C(12/3,6/3)+φ(6)C(12/6,6/6)
　=C(12,6)+C(6,3)+2C(4,2)+2C(2,1)=960
となります。

反転に対する不変配置についてはまた後日。