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 を証明せよ。
ステップ 5/5: 漸化式を望遠鏡和にする
前のステップ次のステップ
ざっくり言うと

トーシェントによる漸化式は、和ごとに分類した互いに素な順序対をちょうど数える。

Mn=1+∑s=2nφ(s)=N+1M_n=1+\sum_{s=2}^{n}\varphi(s)=N+1
詳しい解説

基底は n=2n=2 のとき M2=2M_2=2。s=3,…,ns=3,\ldots,n では非線形環は一通りだけ拡張できるので、Ms=Ms−1+φ(s)M_s=M_{s-1}+\varphi(s)。従って Mn=1+∑s=2nφ(s)M_n=1+\sum_{s=2}^n\varphi(s)。各 ss で、互いに素な正整数対 (x,y)(x,y) かつ x+y=sx+y=s、gcd⁡(x,y)=1\gcd(x,y)=1 の個数は φ(s)\varphi(s) だから、N=∑s=2nφ(s)N=\sum_{s=2}^n\varphi(s)、ゆえに M=N+1M=N+1。