{1,2,...,n}的和能被 m 整除的 m 元子集

王守恩

王守恩 发表于 2021-8-17 08:18
我们可以这样说吗？m 为奇素数，有：\(F(n,m)=\lfloor\frac{C_{n}^m}{m}\rfloor+\lfloor\frac{n}{m}\rf ...

对32楼作强化。m 为奇素数，有：\(F(n,m)=\frac{n!/m}{m!(n-m)!}-\frac{(1-m)\lfloor m/n\rfloor}{m}=\lfloor\frac{n!/m}{m!(n-m)!}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m^2}\rfloor\)

这3者之间还是有区别的。

大胆猜测1：m=4, 5, 6, 7,  ...
\((\frac{n!/m}{m!(n-m)!}-\frac{(1-m)\lfloor m/n\rfloor}{m})-(\lfloor\frac{n!/m}{m!(n-m)!}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m^2}\rfloor)=0\)(所有项都是0) 则：m 为奇素数。在这里:\((m+\lfloor\sqrt{m}\rfloor)≤n≤(m+\lfloor\sqrt{m}\rfloor+\lfloor\ln(m/\pi)\rfloor)\)
{{1/2}, {0}, {1/2}, {0}, {1/2}, {1/3, 1/3}, {1/2, 0}, {0, 0}, {5/6, 7/12}, {0, 0}, {1/2, 1/2}, {1/3, 1/3}, {3/4, 3/4}, {0, 0}, {1/3, 1/3}, {0, 0},{1/4, 9/20},
{1/3, 1/3}, {1/2, 1/2}, {0, 0}, {1/12, 1/12, 7/12}, {1/5, 1/5, 1/5}, {0, 1/2, 1/2}, {1/3, 0, 0}, {1/4, 1/4, 11/28}, {0, 0, 0}, {1/30, 11/30, 11/30},{0, 0, 0},
{3/4, 1/4, 1/4}, {1/3, 1/3, 1/3}, {0, 1/2, 1/2}, {1/5, 1/5, 12/35}, {1/4, 1/4, 1/2}, {0, 0, 0}, {1/2, 1/2, 0}, {2/3, 2/3, 2/3}, {9/20, 9/20, 33/40}, {0, 0, 0},

大胆猜测2：m=10, 11, 12, 13, ...
\(F(n,m)-(\lfloor\frac{n!/m}{m!(n-m)!}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m^2}\rfloor)\)=C, C是整数，特别地，当C=0时，则：m 为奇素数。在这里(n只有1项):\(n=m+\lfloor\sqrt{m}\rfloor\)
{1, 0, 1, 0, 1, 1, 3, 0, 3, 0, 2, 1, 4, 0, 4, 1, 5, 1, 3, 0, 4, 0, 5, 1, \6, 1, 41, 0, 41, 6, 45, 0, 43, 0, 51, 7, 57, 0, 68,}

大胆猜测3：m=10, 11, 12, 13, ...
\(F(n,m)-(\frac{n!/m}{m!(n-m)!}-\frac{(1-m)\lfloor m/n\rfloor}{m})\)=C, C是分数，特别地，当C=0时，则：m 为奇素数。在这里(n只有1项):\(n=m+\lfloor\sqrt{m}\rfloor\)
{3/2, 0, 1/6, 0, 3/2, 2/3, 9/4, 0, 10/3, 0, 7/4, 2/3, 9/2, 0, 47/12, 4/5, 5, 2/3, 11/4, 0, 121/30, 0, 17/4, 2/3, 6, 4/5, 163/4, 0, 83/2, 16/3, 891/20, 0, 263/6,}

还是那句话：帖子是论坛共同的财富，各位网友：可有反例？

TSC999

对于 39# 楼 mathe 给出的 m 为任何正整数的统一公式，这公式用 mathematica 代码计算是：

1. Clear["Global`*"];
   
2. F[n_,m_]:=1/m DivisorSum[m, (-1)^(m-#)EulerPhi[m/#] Binomial[\[LeftFloor]# n/m\[RightFloor], #]&]

复制代码

以n=20,m=10为例，计算结果为：F(20,10)=18452

TSC999

王守恩 发表于 2021-8-18 16:44
尊敬的mathe! 太厉害了！不是想学就能学的。只能仰望，差距太大，得用光年计算：一万光年。
看33楼 ...

1. Clear["Global`*"];
   
2. F[n_,m_]:=1/m DivisorSum[m, (-1)^(m-#)EulerPhi[m/#] Binomial[\[LeftFloor]# n/m\[RightFloor], #]&]
   
3. Table[{{n,25},F[n,25]}, {n, 25, 100}]//MatrixForm

复制代码

运行结果：
{
{{25, 25}, 1},
{{26, 25}, 2},
{{27, 25}, 15},
{{28, 25}, 132},
{{29, 25}, 951},
{{30, 25}, 5702},
{{31, 25}, 29453},
{{32, 25}, 134636},
{{33, 25}, 555368},
{{34, 25}, 2098052},
{{35, 25}, 7343180},
{{36, 25}, 24032216},
{{37, 25}, 74099324},
{{38, 25}, 216598016},
{{39, 25}, 603380180},
{{40, 25}, 1609013812},
{{41, 25}, 4123097878},
{{42, 25}, 10186477096},
{{43, 25}, 24334361938},
{{44, 25}, 56353259212},
{{45, 25}, 126794833226},
{{46, 25}, 277741063232},
{{47, 25}, 593355907790},
{{48, 25}, 1238307981452},
{{49, 25}, 2528212128776},
{{50, 25}, 5056424257552},
{{51, 25}, 9918370659004},
{{52, 25}, 19102047195080},
{{53, 25}, 36157446476364},
{{54, 25}, 67327658955952},
{{55, 25}, 123434041419244},
{{56, 25}, 222977623208896},
{{57, 25}, 397178891340787},
{{58, 25}, 698071990841326},
{{59, 25}, 1211360219401069},
{{60, 25}, 2076617518973260},
{{61, 25}, 3518713018260157},
{{62, 25}, 5896221814381798},
{{63, 25}, 9775315113317107},
{{64, 25}, 16041542750058760},
{{65, 25}, 26067506968845484},
{{66, 25}, 41962328291312116},
{{67, 25}, 66939904655188252},
{{68, 25}, 105858453873320836},
{{69, 25}, 166005302664980284},
{{70, 25}, 258230470812191552},
{{71, 25}, 398573117992730264},
{{72, 25}, 610580095648437680},
{{73, 25}, 928590562131998804},
{{74, 25}, 1402361257097304152},
{{75, 25}, 2103541885645956228},
{{76, 25}, 3134689868805738456},
{{77, 25}, 4641752305731574020},
{{78, 25}, 6831258110321938896},
{{79, 25}, 9993877605841354828},
{{80, 25}, 14536549244860152476},
{{81, 25}, 21026080157744148804},
{{82, 25}, 30248045139210880428},
{{83, 25}, 43285995630250052724},
{{84, 25}, 61627519202389905276},
{{85, 25}, 87305652203385699140},
{{86, 25}, 123086657204773280348},
{{87, 25}, 172718373819601215572},
{{88, 25}, 241257411049601697548},
{{89, 25}, 335498587240852360265},
{{90, 25}, 464536505410410960366},
{{91, 25}, 640497302914354505439},
{{92, 25}, 879488833852546484568},
{{93, 25}, 1202830316886570926919},
{{94, 25}, 1638638402715038653566},
{{95, 25}, 2223866403684695315553},
{{96, 25}, 3006917954277897890796},
{{97, 25}, 4050986688402167991120},
{{98, 25}, 5438310896759074836756},
{{99, 25}, 7275578091610113632328},
{{100, 25}, 9700770788813484843104}
}
有了 mathe  的这个通用公式，随便你要什么数据都不是问题。

mathe

math.stackexchange上有人解决了这个问题，
首先有q-binomial theorem
\[\prod_{k=0}^{n-1}(1+q^k t)=\sum_{k=0}^n q^{k(k-1)/2} {n\choose k}_q t^k\]
其中\({m\choose r}_q = \frac{(1-q^m)(1-q^{m-1})\cdots(1-q^{m-r+1})}{(1-q)(1-q^2)\cdots(1-q^r)}\)
于是比较系数，我们可以得到
\[q^{t\choose 2}{n\choose t}_q = \sum_{X \subset\{1,2,\cdots,n\},|X|=t}q^{\sigma(X)}\]特别t=m时就对应我们要求的情况
其中\(\sigma(X)\)代表集合X中所有元素之和。
后面选择$q=e^{(i2\pi k)/m}$代入，于是\(q^{m \choose 2}=(-1)^{k(m-1)}\)后面还需要在等式另外一边消去奇点可得.

mathe

现在我们设
\[q^{m\choose 2}{n\choose m}_q=\sum_{X\subset\{1,2,\dots,n\},|X|=m}q^{\sigma(X)}=\sum a_i q^i\]
于是$F(n,m)=\sum_{i|m} a_i$
于是分别将$q=\exp(\frac{2ik\pi}m)$代入上面表达式，可以得出
\[F(n,m)=\frac1m \sum_{k=0}^{m-1} (-1)^{(m-1)k}{n\choose m}_{exp(\frac{2ik\pi}m)}\]
现在假设$q=\omega_m^k = \exp(\frac{2ik\pi}m) = \omega_d^u$是d次单位根,即(k,m)=d, k=du,
将结果代入\({n\choose m}_q=\)时分子分母会同时出现很多取零的项，记\(n'=\lfloor\frac n d\rfloor\)
而其中所有非零项都可以相互抵消,于是结果就变成
$\lim_{q\to \omega_d^u}\frac{(1-q^{n'd})(1-q^{(n'-1)d})\cdots (1-q^{(n'-u+1)d})}{(1-q^d)(1-q^{2d})\cdots (1-q^{ud})}$
而其中$\lim_{q\to\omega_d^u} \frac{1-q^{(n'-h+1)d}}{1-q^{hd}}$根据洛比特法则可以得出为$\frac{n'-h+1}h q^{n'd}=\frac{n'-h+1}h$
所以乘积结果为\(\prod_{h=1}^u \frac{n'-h+1}h={n'\choose u}\)
由于满足(k,m)=d的k共有$\varphi(d)$个，于是最终结果就变成
\[F(n,m)=\frac1m \sum_{u|m} (-1)^{(m-1) u}\varphi(\frac m u){\lfloor\frac {n u}m \rfloor\choose u}\]

类似，可以有
\[F_h(n,m)=\frac1m \sum_{k=0}^{m-1} (-1)^{(m-1)k}\omega_m^{m-h}{n\choose m}_{exp(\frac{2ik\pi}m)}=\frac1m \sum_{u|m}^m (-1)^{(m-1)u} \sum_{1\le k\le m, (k,m)=u}\omega_m^{-kh}{\lfloor\frac {n u}m \rfloor\choose u}\]

而\[\sum_{1\le k\le m, (k,m)=u}\omega_m^{-kh}=u \sum_{1\le k\le m/u, (k,m/u)=1}\omega_{m/u}^{-kh}\]
设\((m/u,h)=r\),于是上式等于\(u r\mu(\frac m{u r})\), 即最终结果为
\[F_h(n,m)=\frac1m \sum_{u|m, r=(m/u,h)} (-1)^{m-u} u r \mu(\frac m{u r}){\lfloor\frac {n u}m \rfloor\choose u}\]
其中$\mu(x)$为莫比乌斯函数，在x的某个素数因子次数大于1时为0，不然，素因子数目偶数时为1，奇数时为-1.