MathLabs

第6题

设 n≥2n\ge2 为整数,在圆周上标出 n+1n+1 个等间距的点。考虑用 0,1,…,n0,1,\ldots,n 对这些点作标号、每个数恰用一次的所有方式;若一种标号可由另一种经圆的旋转得到,则视为相同的标号。称一种标号是美丽的,如果对任意满足 a+d=b+ca+d=b+c 的四个标号 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=sx+y=s 且 gcd⁡(x,y)=1\gcd(x,y)=1 的互素正整数对 (x,y)(x,y) 数量为 φ(s)\varphi(s)，故 N=∑s=2nφ(s)N=\sum_{s=2}^n\varphi(s)，最终 M=N+1M=N+1。