MathLabs

第6問

n≥2n\ge2 を整数とし、円周上に等間隔に印をつけた n+1n+1 個の点を考える。これらの点に 0,1,…,n0,1,\ldots,n を1回ずつ用いてラベル付けするすべての方法を考える。円の回転で一方から他方が得られるとき、2つのラベル付けは同じものとみなす。ラベル付けが美しいとは、a+d=b+ca+d=b+c を満たす任意の4つのラベル a<b<c<da<b<c<d について、ラベル aa と dd の点を結ぶ弦が、ラベル bb と cc の点を結ぶ弦と交わらないことをいう。MM を美しいラベル付けの個数、NN を x+y≤nx+y\le n かつ gcd⁡(x,y)=1\gcd(x,y)=1 を満たす正の整数の順序対 (x,y)(x,y) の個数とする。M=N+1M=N+1 を証明せよ。
ステップ 4/5: 非線形環と線形環の拡張を数える
前のステップ次のステップ
ざっくり言うと

非線形環では n の挿入位置が一つ、線形環では 0 に隣接する二つであり、線形環の個数はオイラーのトーシェントで数えられる。

Ln−1=φ(n),Mn=Mn−1+φ(n)L_{n-1}=\varphi(n),\qquad M_n=M_{n-1}+\varphi(n)
詳しい解説

非線形環では擬平行な n-弦により n の位置は高々一つであり、そこへ挿入すれば美しい。禁じられた交差があれば n-弦に関して反射して元の禁じられた交差が得られるからである。線形環では n は 0 の時計回りまたは反時計回りの直隣にしか置けず、どちらも美しい。{0,…,n−1}\{0,\ldots,n-1\} 上の線形環は n と互いに素なステップで定まり、その個数は φ(n)\varphi(n)。その個数を Ln−1L_{n-1} とすれば Mn=Mn−1+Ln−1=Mn−1+φ(n)M_n=M_{n-1}+L_{n-1}=M_{n-1}+\varphi(n)。