对于任意M,我们同样可以假设从1，2,...,kM中选择u个数，这u个数的和模M为h的不同组合情况为$C_M(u,kM,h)$,
我们可以先查看从0,1,2,...,M-1中选择u个数（每个数最多可以重复k次),这u个数的和模M为h的所有模式，
其中比如某个模式中有$a_0$个0，$a_1$个1，..., $a_{M-1}$个M-1. 于是$a_0+a_1+...+a_{M-1}=u$, 而且这种模式回归到原题对
$C_M(u,kM,h)$贡献了$C_k^{a_0}C_k^{a_1}...C_k^{a_{M-1}}$种情况，这时k的一个M次多项式。所以所有这些模式得到的计数之和$C_M(u,kM,h)$也是k的M次多项式。
同样，如果我们查看$C_M(u,kM+1,h)$， 那么我们同样根据其中0,1,...,M-1的数目得出所有模式，区别是$a_1$最大有k+1个选择，得出各个模式的贡献为$C_k^{a_0}C_{k+1}^{a_1}C_k^{a_2}...C_k^{a_{M-1}}$这同样是k的一个M次多项式。
所以$C_M(u,n,h)$,特别是$F(n,M)=C_M(M,n,0)$可以根据n%M表示为M个$\lfloor\frac nM\rfloor$的M次多项式。
本帖最后由 王守恩 于 2021-8-17 09:56 编辑
TSC999 发表于 2021-8-1 08:40
对于 m 为奇素数，@王守恩 拟出了一个与陆教授公式等价的公式：\begin{equation}F(n, m)=\left\lfloor{\fra ...
我们可以这样说吗？m 为奇素数，有：\(F(n,m)=\lfloor\frac{C_{n}^m}{m}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m^2}\rfloor\)，倒回去：
若 \(\lfloor\frac{C_{n}^m}{m}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m^2}\rfloor-F(n,m)=0\)则：m 为奇素数。在这里 \(m<n<4m/3\)
或(从33楼来的)，m 为奇素数，有：\(F(n,m)=\frac{n!/m}{m!(n-m)!}-\frac{(1-m)\lfloor n/m\rfloor}{m}\)，倒回去：
若 \(\frac{n!/m}{m!(n-m)!}-\frac{(1-m)\lfloor n/m\rfloor}{m}-F(n,m)=0\)则：m 为奇素数。在这里 \(m<n<4m/3\)
根据楼上的结论可以看出2#的公式(3) (m=2)时的结论是错误的，因为分别去n为奇数和偶数，结果不是的多项式。
通过一段简单的Pari/gp代码可以直接计算出m个关于k的多项式 (设n=km+r):
getPolys(m)={
local(C, P, H, R, r);
C=getC(m*(m+1),m);
H=matrix(m+1,m+1);
for(u=1,m+1,
H=1;
for(v=1,m, H=(u-1)^v)
);
R=matrix(m+1,m);
for(u=1,m+1,
for(v=1,m,
R=C[(u-1)*m+v]
)
);
R=H^-1*R;
P=vector(m);
for(u=1,m,
P=R;
for(v=1,m,
if(u==m, P*=k-1,P*=k);
P+=R
)
);
P
}
比如
getPolys(2)
%10 =
代表n为奇数时，结果为k^2 (k=(n-1)/2), 而n为偶数时，结果为k^2-k (k=n/2)
同样:
? getPolys(3)
%11 =
代表n=3k+1时，结果为3/2*k^3 + 1/2*k; n=3k+2时，结果为3/2*k^3 + 3/2*k^2 + k, n=3k时，结果为3/2*k^3 - 3/2*k^2 + k
类似有
? getPolys(2)
%10 =
? getPolys(3)
%11 =
? getPolys(4)
%12 =
? getPolys(5)
%13 =
? getPolys(6)
%14 =
? getPolys(7)
%15 =
? getPolys(8)
%16 =
? getPolys(9)
%17 =
? getPolys(10)
%18 =
? getPolys(11)
%19 =
? getPolys(12)
%20 =
? getPolys(13)
%21 =
? getPolys(14)
%22 =
? getPolys(15)
%23 =
? getPolys(16)
%25 =
但是这个表达式很难看，考虑到结果应该很接近$\frac{C_n^m}m$,我们从结果中减去$\frac{C_n^m}m$,得到
? getPolysd(2)
%27 = [-1/2*k, -1/2*k]
? getPolysd(3)
%28 =
? getPolysd(4)
%29 =
? getPolysd(5)
%30 =
? getPolysd(6)
%31 = [-3/4*k^3 + 17/12*k^2 - 5/6*k, -3/4*k^3 + 2/3*k^2 - 7/12*k, -3/4*k^3 + 2/3*k^2 + 1/12*k, -3/4*k^3 - 1/12*k^2 - 1/6*k, -3/4*k^3 - 1/12*k^2 - 1/6*k, -3/4*k^3 + 17/12*k^2 - 5/6*k]
? getPolysd(7)
%32 =
? getPolysd(8)
%33 =
? getPolysd(9)
%34 =
? getPolysd(10)
%35 = [-125/48*k^5 + 125/24*k^4 - 175/48*k^3 + 221/120*k^2 - 9/10*k, -125/48*k^5 + 125/48*k^4 - 25/48*k^3 + 167/240*k^2 - 31/40*k, -125/48*k^5 + 125/48*k^4 - 25/48*k^3 + 167/240*k^2 - 31/40*k, -125/48*k^5 + 25/48*k^3 + 4/5*k^2 - 49/60*k, -125/48*k^5 + 25/48*k^3 + 4/5*k^2 - 1/60*k, -125/48*k^5 - 125/48*k^4 - 25/48*k^3 + 217/240*k^2 + 1/40*k, -125/48*k^5 - 125/48*k^4 - 25/48*k^3 + 217/240*k^2 + 1/40*k, -125/48*k^5 - 125/24*k^4 - 175/48*k^3 - 29/120*k^2 - 1/10*k, -125/48*k^5 - 125/24*k^4 - 175/48*k^3 - 29/120*k^2 - 1/10*k, -125/48*k^5 + 125/24*k^4 - 175/48*k^3 + 221/120*k^2 - 9/10*k]
? getPolysd(11)
%36 =
? getPolysd(12)
%37 =
? getPolysd(13)
%38 =
? getPolysd(14)
%39 = [-16807/1440*k^7 + 16807/480*k^6 - 12005/288*k^5 + 2401/96*k^4 - 1421/180*k^3 + 583/280*k^2 - 13/14*k, -16807/1440*k^7 + 16807/720*k^6 - 2401/144*k^5 + 343/72*k^4 - 343/1440*k^3 + 3781/5040*k^2 - 71/84*k, -16807/1440*k^7 + 16807/720*k^6 - 2401/144*k^5 + 343/72*k^4 - 343/1440*k^3 + 3781/5040*k^2 - 71/84*k, -16807/1440*k^7 + 16807/1440*k^6 - 2401/1440*k^5 - 343/288*k^4 + 49/180*k^3 + 2209/2520*k^2 - 181/210*k, -16807/1440*k^7 + 16807/1440*k^6 - 2401/1440*k^5 - 343/288*k^4 + 49/180*k^3 + 2209/2520*k^2 - 181/210*k, -16807/1440*k^7 + 2401/720*k^5 - 343/1440*k^3 + 6/7*k^2 - 239/280*k, -16807/1440*k^7 + 2401/720*k^5 - 343/1440*k^3 + 6/7*k^2 + 1/280*k, -16807/1440*k^7 - 16807/1440*k^6 - 2401/1440*k^5 + 343/288*k^4 + 49/180*k^3 + 2111/2520*k^2 - 1/210*k, -16807/1440*k^7 - 16807/1440*k^6 - 2401/1440*k^5 + 343/288*k^4 + 49/180*k^3 + 2111/2520*k^2 - 1/210*k, -16807/1440*k^7 - 16807/720*k^6 - 2401/144*k^5 - 343/72*k^4 - 343/1440*k^3 + 4859/5040*k^2 + 1/84*k, -16807/1440*k^7 - 16807/720*k^6 - 2401/144*k^5 - 343/72*k^4 - 343/1440*k^3 + 4859/5040*k^2 + 1/84*k, -16807/1440*k^7 - 16807/480*k^6 - 12005/288*k^5 - 2401/96*k^4 - 1421/180*k^3 - 103/280*k^2 - 1/14*k, -16807/1440*k^7 - 16807/480*k^6 - 12005/288*k^5 - 2401/96*k^4 - 1421/180*k^3 - 103/280*k^2 - 1/14*k, -16807/1440*k^7 + 16807/480*k^6 - 12005/288*k^5 + 2401/96*k^4 - 1421/180*k^3 + 583/280*k^2 - 13/14*k]
? getPolysd(15)
%40 =
? getPolysd(16)
%41 =
? getPolysd(18)
%42 = [-531441/8960*k^9 + 531441/2240*k^8 - 255879/640*k^7 + 60201/160*k^6 - 282807/1280*k^5 + 27067/320*k^4 - 47451/2240*k^3 + 20401/5040*k^2 - 17/18*k, -531441/8960*k^9 + 1594323/8960*k^8 - 137781/640*k^7 + 89901/640*k^6 - 78687/1280*k^5 + 29941/1280*k^4 - 1119/140*k^3 + 52201/20160*k^2 - 127/144*k, -531441/8960*k^9 + 1594323/8960*k^8 - 137781/640*k^7 + 89901/640*k^6 - 69471/1280*k^5 + 14581/1280*k^4 - 139/140*k^3 + 18601/20160*k^2 - 539/720*k, -531441/8960*k^9 + 531441/4480*k^8 - 373977/4480*k^7 + 1773/64*k^6 - 11151/1280*k^5 + 2147/640*k^4 - 1909/2240*k^3 + 2095/2016*k^2 - 1909/2520*k, -531441/8960*k^9 + 531441/4480*k^8 - 373977/4480*k^7 + 1773/64*k^6 - 11151/1280*k^5 + 2147/640*k^4 - 1909/2240*k^3 + 2095/2016*k^2 - 1909/2520*k, -531441/8960*k^9 + 531441/8960*k^8 - 19683/4480*k^7 - 1953/640*k^6 - 387/256*k^5 - 713/1280*k^4 - 59/560*k^3 + 13807/20160*k^2 - 3131/5040*k, -531441/8960*k^9 + 531441/8960*k^8 - 19683/4480*k^7 - 1953/640*k^6 - 387/256*k^5 - 713/1280*k^4 - 59/560*k^3 + 13807/20160*k^2 - 3131/5040*k, -531441/8960*k^9 + 19683/896*k^7 + 36/5*k^6 - 7767/1280*k^5 - k^4 + 41/448*k^3 + 31/45*k^2 - 157/252*k, -531441/8960*k^9 + 19683/896*k^7 + 36/5*k^6 + 1449/1280*k^5 - k^4 - 407/448*k^3 + 31/45*k^2 + 83/1260*k, -531441/8960*k^9 - 531441/8960*k^8 - 19683/4480*k^7 + 11169/640*k^6 + 7281/1280*k^5 - 1847/1280*k^4 - 619/560*k^3 + 13969/20160*k^2 + 341/5040*k, -531441/8960*k^9 - 531441/8960*k^8 - 19683/4480*k^7 + 11169/640*k^6 + 7281/1280*k^5 - 1847/1280*k^4 - 619/560*k^3 + 13969/20160*k^2 + 341/5040*k, -531441/8960*k^9 - 531441/4480*k^8 - 373977/4480*k^7 - 4257/320*k^6 + 16497/1280*k^5 + 4253/640*k^4 + 331/2240*k^3 + 53/10080*k^2 - 341/2520*k, -531441/8960*k^9 - 531441/4480*k^8 - 373977/4480*k^7 - 4257/320*k^6 + 16497/1280*k^5 + 4253/640*k^4 + 331/2240*k^3 + 53/10080*k^2 - 341/2520*k, -531441/8960*k^9 - 1594323/8960*k^8 - 137781/640*k^7 - 16137/128*k^6 - 41823/1280*k^5 - 1781/1280*k^4 + 1/140*k^3 + 491/4032*k^2 - 91/720*k, -531441/8960*k^9 - 1594323/8960*k^8 - 137781/640*k^7 - 16137/128*k^6 - 32607/1280*k^5 + 13579/1280*k^4 + 981/140*k^3 + 7211/4032*k^2 + 1/144*k, -531441/8960*k^9 - 531441/2240*k^8 - 255879/640*k^7 - 57897/160*k^6 - 236727/1280*k^5 - 16187/320*k^4 - 13851/2240*k^3 + 1663/5040*k^2 - 1/18*k, -531441/8960*k^9 - 531441/2240*k^8 - 255879/640*k^7 - 57897/160*k^6 - 236727/1280*k^5 - 16187/320*k^4 - 13851/2240*k^3 + 1663/5040*k^2 - 1/18*k, -531441/8960*k^9 + 531441/2240*k^8 - 255879/640*k^7 + 60201/160*k^6 - 282807/1280*k^5 + 27067/320*k^4 - 47451/2240*k^3 + 20401/5040*k^2 - 17/18*k]
? getPolysd(20)
%43 =
? getPolysd(21)
%44 =
而从上面结论中可以看出在m为奇素数时，更简洁的表达式为$F(n,m)=\frac{C_n^m}m+\frac{m-1}m\lfloor\frac nm\rfloor$或者$F(n,m)=\frac{C_n^m-\lfloor\frac nm\rfloor}m+\lfloor\frac nm\rfloor$ 。
本帖最后由 王守恩 于 2021-8-17 09:12 编辑
王守恩 发表于 2021-8-5 11:12
这题目不太好做。
先看一串数。
这题目还是不太好做。
再看一串数(应该是这串数吧？我们已经有6个数了，请网友验证)。
m=02，通项公式1次项(最高项)系数=1/2
m=04，通项公式2次项(最高项)系数=1/2
m=06，通项公式3次项(最高项)系数=3/4
m=08，通项公式4次项(最高项)系数=4/3
m=10，通项公式5次项(最高项)系数=125/48
m=12，通项公式6次项(最高项)系数=27/5
......
{1/2,1/2,3/4,4/3,125/48,27/5,16807/1440,8192/315,531441/8960,78125/567,2357947691/7257600,
1492992/1925, 1792160394037/958003200, 3954653486/868725, 320361328125/28700672, 17592186044416/638512875,
2862423051509815793/41845579776000,2541865828329/14889875,5480386857784802185939/12804747411456000,
16000000000000000/14849255421, 41209797661291758429/15135211520000, 122318180896829092582/17717861581875,
39471584120695485887249589623/2248001455555215360000, 112190507323565801472/2505147019375, ......}
通项公式\(=\frac{m^m}{2m*m!}\)
公式为\[\sum_{d|m} c(m/d) C_{}^d\]
其中系数c(m/d)需要测试一下，好像c(2)=-1,其它情况c(x)=x-1? 不过还需要检验一下，最后一项系数好像不对，但是大部分对上了
\[\frac1m\sum_{d|m} c(m,d) C_{}^d\]
c(m,d)的分布
c(3,.)={1->2, 3->1}
c(4,.)={1->-2,2->1,4->1}
c(5,.)={1->4,5->1}
c(6,.)={1->-2,2->2,3->-1,6->1}
c(7,.)={1->6,7->1}
c(8,.)={1->-4,2->2,4->1,8->1}
c(9,.)={1->6,3->2,9->1}
c(10,.)={1->-4,2->4,5->-1,10->1}
c(11,.)={1->10,11->1}
c(12,.)={1->-4,2->2,3->-2,4->2,6->1,12->1}
c(13,.)={1->12,13->1}
c(14,.)={1->-6,2->6,7->-1,14->1}
c(15,.)={1->8,3->4,5->2,15->1}
c(16,.)={1->-8,2->4,4->2,8->1,16->1}
c(18,.)={1->-6,2->6,3->-2,6->2,9->-1,18->1}
c(20,.)={1->-8,2->4,4->4,5->-2,10->1,20->1}
c(21,.)={1->12,3->6,7->2,21->1}
c(22,.)={1->-10,2->10,11->-1,22->1}
c(24,.)={1->-8,2->4,3->-4,4->2,6->2,8->2,12->1,24->1}
c(25,.)={1->20,5->4,25->1}
c(26,.)={1->-12,2->12,13->-1,26->1}
c(27,.)={1->18,3->6,9->2,27->1}
c(28,.)={1->-12,2->6,4->6,7->-2,14->1,28->1}
c(30,.)={1->-8,2->8,3->-4,5->-2,6->4,10->2,15->-1,30->1}
c(32,.)={1->-16,2->8,4->4,8->2,16->1,32->1}
c(33,.)={1->20,3->10,11->2,33->1}
c(34,.)={1->-16,2->16,17->-1,34->1}
c(35,.)={1->24,5->6,7->4,35->1}
c(36,.)={1->-12,2->6,3->-4,4->6,6->2,9->-2,12->2,18->1,36->1}
所以$C(m,d)=(-1)^(m-d) \varphi(\frac md)$, 即\}^d\]
`C_{}^d`小罐装大罐，吃相有点难看呵:lol ，咱们换大点的罐子\[
\text{F}(n,m)=\frac1m\sum_{d|m} (-1)^{m-d} \varphi\left(\frac md\right)\begin{pmatrix}\\d\end{pmatrix}
\]
如果我们继续扩展，好像可以有
\\choose d}\]
其中表格c(m,d,h)我现在还没有找出规律
比如m=12,横向为d,纵向为h,可以有表格
\[\begin{matrix}m=12&\begin{matrix}1&2&3&4&6&12\end{matrix}\\
\begin{matrix} 1\\ 2\\ 3\\ 4\\ 6\\ 12\end{matrix}&\begin{bmatrix}0&1&0&-1&-1&1\\-2&-1&2&-1&1&1\\0&-2&0&2&-1&1\\2&-1&-2&-1&1&1\\4&2&2&2&1&1\\-4&2&-2&2&1&1\end{bmatrix}\end{matrix}\]
而比如m=8,可以有
\[\begin{matrix}m=8&\begin{matrix}1&2&4&8\end{matrix}\\
\begin{matrix} 1\\ 2\\ 4\\ 8\end{matrix}&
\begin{bmatrix}0&0&-1&1\\0&-2&1&1\\4&2&1&1\\-4&2&1&1\end{bmatrix}\end{matrix}\]
而比如m=4,可以有
\[\begin{matrix}m=4&\begin{matrix}1&2&4\end{matrix}\\
\begin{matrix} 1\\ 2\\ 4\end{matrix}&
\begin{bmatrix}0&-1&1\\2&1&1\\-2&1&1\end{bmatrix}\end{matrix}\]
而比如m=9,可以有
\[\begin{matrix}m=9&\begin{matrix}1&3&9\end{matrix}\\
\begin{matrix} 1\\ 3\\ 9\end{matrix}&
\begin{bmatrix}0&-1&1\\-3&2&1\\6&2&1\end{bmatrix}\end{matrix}\]
而比如m=16,可以有
\[\begin{matrix}m=16&\begin{matrix}1&2&4&8&16\end{matrix}\\
\begin{matrix} 1\\ 2\\ 4\\ 8\\ 16\end{matrix}&
\begin{bmatrix}0&0&0&-1&1\\0&0&-2&1&1\\0&-4&2&1&1\\8&4&2&1&1\\-8&4&2&1&1\end{bmatrix}\end{matrix}\]
分析结果好像如下,定义有理数域中函数g(x)如下,
\(g(p^a)=\begin{cases}0&a\ge2\\\frac1{1-p}&a==1\\1&a\le0\end{cases}\)
\(g(p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t})=g(p_1^{a_1})g(p_2^{a_2})\cdots g(p_t^{a_t})\)
那么$c(m,d,h)=(-1)^{m-d}\varphi(\frac m d)g(\frac{m}{dh})$
即
\\choose d}\]
CNM(n,m)=if(n<m,0,n!/m!/(n-m)!)
getG(n)={
local(v,p);
v=factor(n);p=1;
for(x=1,length(v[,1]),
if(v>=2, p=0;break());
if(v==1, p*=1/(1-v))
);
p
}
Fh(n,m,h)={
local(s,k,d);
s=0;d=divisors(m);
for(u=1,length(d),
s+=(-1)^(m-d)*eulerphi(m/d)*getG(m/(d*gcd(h,m)))*CNM(floor(d*n/m),d)
);
s/m
}
上面代码出来的结果我验算了$F_3(1..200,15), F_{15}(1..2000,180)$,结果都能够匹配，所以应该问题不大了
本帖最后由 王守恩 于 2021-8-18 20:18 编辑
mathe 发表于 2021-8-16 13:16
M=12
尊敬的mathe! 太厉害了！不是想学就能学的。只能仰望，差距太大，得用光年计算：一万光年。
看33楼：接下来25应该是最简单的，我还就不信(6个数能找出规律，数多了反而不好找了？)
在 1～n 中任意取 25 个不同整数，使得这 25 个数之和能被 25 整除，有几种不同取法？
Table[\(\D\sum_{k=24}^n\)(Count/25, _Integer]), {n, 24,33}]
{1, 2, 15, 132, 951, 5702, 29453, 134636, 555368, 2098052}
这里是n=33(再怎么鼓捣，出不来了)，如果要搞个通项，需要n=25——95，能来几项？谢谢！