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

TSC999

{1,2,...,n}的所有 m 元子集中，和能被 m 整除的有多少个？

（一）如果 m 为奇质数，则共有 \begin{equation}\text{F}(n, m)=\left\lceil\frac{C_n^m+4\left\lfloor{\frac n m}\right\rfloor}m\right\rceil\end{equation} 个合情子集。
式中 \(\lceil\quad\rceil\) 表示 “向上” 取整，\(\lfloor\quad\rfloor\) 表示 “向下” 取整。
这是【数学中国】论坛管理员陆元鸿教授给出的, 试证明陆教授的上述公式或举出反例否证。

（二）当 m 不为奇质数时，F(n, m) 的计算公式是什么样？


补充内容 (2021-8-15 19:24):
说明一下，上面这个陆教授公式，其实陆提出时只限于 m=5 情况，且没有向上取整符号。是我凭猜想 “推广” 了这个公式并且增加了向上取整符号。这个公式经 mathe 证明是有错的，这个错误是我的，不是陆教授的。

TSC999

下面是一个验证公式的 mathematica 程序代码。 以 n=20，m=7 为例。

1. m=7; n=20; k=0;
   
2. a=Subsets[Range@n, {m}];
   
3. L=Length[a];
   
4. Do[If[Mod[Total@a[[i]], m]==0, k++], {i, 1, L}];
   
5. Print[k]
   
6. \[LeftCeiling](Binomial[n, m]+4\[LeftFloor]n/m\[RightFloor])/m\[RightCeiling]

复制代码

程序运行结果为：
11076
11076
搜索结果与公式计算值一致。

TSC999

对于 m 为奇素数，@王守恩 拟出了一个与陆教授公式等价的公式：\begin{equation}F(n, m)=\left\lfloor{\frac{C_n^m}m}\right\rfloor+\left\lfloor{\frac nm}\right\rfloor-\left\lfloor{\frac n{m^2}}\right\rfloor\end{equation}
对于 m=2，王守恩给出了如下公式：\begin{equation} F(n, 2)=\left\lfloor{\frac{C_{n-1}^2}2}\right\rfloor+\left\lfloor{\frac{n-1}2}\right\rfloor-\left\lfloor{\frac{n-1}{2^2}}\right\rfloor\end{equation}

TSC999

2# 楼中的那个验证程序可以简化如下：

1. m=7; n=20; k=0;
   
2. Scan[If[Mod[Total@#,m]==0, k++]&, Subsets[Range@n,{m}]];
   
3. Print[k]
   
4. \[LeftCeiling](Binomial[n,p]+4\[LeftFloor]n/p\[RightFloor])/p\[RightCeiling]

复制代码

因为Scan函数可以直接扫描表。

TSC999

今天折腾出了 \(m=2、4、6、8 \) 的公式如下：\[
F(n,2)=C_n^2/2-\lfloor{n/2}\rfloor/2 \quad ...................................④
\]上式与 ③ 式等价。\[\begin{split}
F(n,4)&=\begin{cases}C_n^4/4+\lfloor{n/4}\rfloor(2\lfloor{n/4}\rfloor-3)/4,n\equiv0,1\pmod{4}\\
C_n^4/4+\lfloor{n/4}\rfloor(2\lfloor{n/4}\rfloor-1)/4,n\equiv2,3\pmod{4}\end{cases}..................⑤
\\\\
F(n,6)&=\begin{cases}C_n^6/6-\lfloor{n/6}\rfloor(9{\lfloor{n/6}\rfloor}^2-17\lfloor{n/6}\rfloor+10)/12,&n\equiv0,1\pmod{6}\\
C_n^6/6-\lfloor{n/6}\rfloor(9{\lfloor{n/6}\rfloor}^2-8\lfloor{n/6}\rfloor+7)/12,&n\equiv2\pmod{6}\\
C_n^6/6-\lfloor{n/6}\rfloor(9{\lfloor{n/6}\rfloor}^2-8\lfloor{n/6}\rfloor-1)/12,&n\equiv3\pmod{6}\\
C_n^6/6-\lfloor{n/6}\rfloor(9{\lfloor{n/6}\rfloor}^2+\lfloor{n/6}\rfloor+2)/12,&n\equiv4,5\pmod{6}\end{cases}................⑥
\\\\
F(n,8)&=\begin{cases}
C_n^8/8+\lfloor{n/8}\rfloor(32{\lfloor{n/8}\rfloor}^3-48{\lfloor{n/8}\rfloor}^2+34\lfloor{n/8}\rfloor-21)/24,&n\equiv0,1\pmod{8}\\
C_n^8/8+\lfloor{n/8}\rfloor(32{\lfloor{n/8}\rfloor}^3-16{\lfloor{n/8}\rfloor}^2+10\lfloor{n/8}\rfloor-17)/24,&n\equiv2,3\pmod{8}\\
C_n^8/8+\lfloor{n/8}\rfloor(32{\lfloor{n/8}\rfloor}^3+16{\lfloor{n/8}\rfloor}^2+10\lfloor{n/8}\rfloor-7)/24,&n\equiv4,5\pmod{8}\\
C_n^8/8+\lfloor{n/8}\rfloor(32{\lfloor{n/8}\rfloor}^3+48{\lfloor{n/8}\rfloor}^2+34\lfloor{n/8}\rfloor-3)/24,&n\equiv6,7\pmod{8}
\end{cases}...⑦\end{split}\]
能否将这些按余数分段的公式合并、统一成一个简单公式？

王守恩

m=8时，公式⑦的合并\[\begin{split}
F(n,8)&=\left(\frac{- 48\lfloor n/8\rfloor^3 + 34\lfloor n/8\rfloor^2 - 21\lfloor n/8\rfloor\ \ \ \ }{24}\right)\left(\lfloor\frac{(n + 7)_8 + 1\ }{8}\rfloor+ \lfloor\frac{(n + 6)_8 + 1\ }{8}\rfloor\right)\\
&+\left(\frac{- 16\lfloor n/8\rfloor^3 + 10\lfloor n/8\rfloor^2 - 17\lfloor n/8\rfloor\ \ \ \ }{24}\right)\left(\lfloor\frac{(n + 5)_8 + 1\ }{8}\rfloor+ \lfloor\frac{(n + 4)_8 + 1\ }{8}\rfloor\right)\\
&+\left(\frac{16\lfloor n/8\rfloor^3 + 10\lfloor n/8\rfloor^2 - 7\lfloor n/8\rfloor\ \ \ \ }{24}\right)\left(\lfloor\frac{(n + 3)_8 + 1\ }{8}\rfloor+ \lfloor\frac{(n + 2)_8 + 1\ }{8}\rfloor\right)\\
&+\left(\frac{48\lfloor n/8\rfloor^3 + 34\lfloor n/8\rfloor^2 - 3\lfloor n/8\rfloor\ \ \ \ }{24}\right)\left(\lfloor\frac{(n + 1)_8 + 1\ }{8}\rfloor+ \lfloor\frac{(n)_8 + 1\ }{8}\rfloor\right)\\
&+8C^8_n+\frac{4\lfloor n/8\rfloor^4}{3}
\end{split}
\]式中 `(n)_8` 表示 `\text{mod}(n,8)`.
{0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 21, 64, 163, 380, 809, 1618, 3048, 5486, 9464, 15774, 25464, 40014,
61332, 91998, 135261, 195376, 277601, 388642, 536647, 731790, 986265, 1315020, 1735752, 2269828,
2942280, 3782932, 4826392, 6113428, 7690960, 9613700, 11944145, 14754530, 18126821, ...................}

王守恩

王守恩 发表于 2021-8-4 09:44
m=8时，公式⑦的合并\[\begin{split}
F(n,8)&=\left(\frac{- 48\lfloor n/8\rfloor^3 + 34\lfloor n/8\rfl ...

这题目不太好做。

先看一串数。
a(n)=Sum[EulerPhi[n/k]*(2 k)!/(2 n k! k!), {k, Divisors[n]}
{1, 2, 4, 10, 26, 80, 246, 810, 2704, 9252, 32066, 112720, 400024, 1432860,
5170604, 18784170, 68635478, 252088496, 930138522, 3446167860, 12815663844,
47820447028, 178987624514, 671825133648, 2528212128776, 9536895064400, 36054433810102}

譬如：第5个数=26，对应题目：在 1～5n 中任意取 5 个不同整数，使得这 5 个数之和能被 5 整除，有几种不同取法？
这26个数这样来找，可能会方便些(只要统计0就可以)。
\(5C_{n}^5\)={0,0,0,0,0}(本行有5个0，余同)
\(10C_{n}^3C_{n}^1C_{n}^1\)={0,0,0,1,4}+{0,0,0,2,3}+{0,1,1,1,2}+{0,1,3,3,3}+{0,2,2,2,4}+{0,3,4,4,4}(本行有10个0)
\(10C_{n}^2C_{n}^2C_{n}^1\)={0,0,1,1,3}+{0,0,1,2,2}+{0,0,2,4,4}+{0,0,3,3,4}+{0,1,1,4,4}+{0,2,2,3,3}(本行有10个0)
\(1C_{n}^1C_{n}^1C_{n}^1C_{n}^1C_{n}^1\)={0,1,2,3,4}(本行有1个0)
合计，\(5+10+10+1=26\)
\(a(n)=5C_{n}^5+10C_{n}^3C_{n}^1C_{n}^1+10C_{n}^2C_{n}^2C_{n}^1+1C_{n}^1C_{n}^1C_{n}^1C_{n}^1C_{n}^1\)
a(n)=1, 52, 603, 3104, 10630, 28506, 64932, 131608, 244359, 423760, 695761, 1092312, 1651988, 2420614, 3451890, ...

譬如：第6个数=80，对应题目：在 1～6n 中任意取 6 个不同整数，使得这 6 个数之和能被 6 整除，有几种不同取法？
这80个数这样来找，可能会方便些(只要统计0就可以)。
\(6C_{n}^6\)={0,0,0,0,0,0}(本行有6个0，余同)
\(6C_{n}^4C_{n}^2\)={0,0,0,0,3,3}+{0,0,3,3,3,3}(本行有6个0)
\(6C_{n}^3C_{n}^3\)={0,0,0,2,2,2}+{0,0,0,4,4,4}(本行有6个0)
\(12C_{n}^4C_{n}^1C_{n}^1\)={0,0,0,0,1,5}+{0,0,0,0,2,4}+{0,1,1,1,1,2}+{0,2,2,2,2,4}+{0,2,4,4,4,4,}+{0,4,5,5,5,5}
\(12C_{n}^3C_{n}^2C_{n}^1\)={0,0,0,1,1,4}+{0,0,0,2,5,5}+{0,0,1,1,1,3}+{0,0,3,5,5,5}+{0,2,2,2,3,3}+{0,3,3,4,4,4}
\(8C_{n}^2C_{n}^2C_{n}^2\)={0,0,1,1,2,2}+{0,0,1,1,5,5}+{0,0,2,2,4,4}+{0,0,4,4,5,5}(本行有8个0)
\(12C_{n}^3C_{n}^1C_{n}^1C_{n}^1\)={000123}{000345}{011145}{012225}{012333}{012555}{014445}{033345}
\(12C_{n}^2C_{n}^2C_{n}^1C_{n}^1\)={001335}{001344}{002334}{002235}{011244}{011335}{022355}{022455}
\(6C_{n}^2C_{n}^1C_{n}^1C_{n}^1C_{n}^1\)={0,0,1,2,4,5}+{0,1,1,2,3,5}+{0,1,2,2,3,4}+{0,1,3,4,5,5}+{0,2,3,4,4,5}
合计，\(6+6+6+12+12+8+12+12+6=80\)
\(a(n)=6C_{n}^6+6C_{n}^4C_{n}^2+6C_{n}^3C_{n}^3+12C_{n}^4C_{n}^1C_{n}^1+12C_{n}^3C_{n}^2C_{n}^1+8C_{n}^2C_{n}^2C_{n}^2+12C_{n}^3C_{n}^1C_{n}^1C_{n}^1+12C_{n}^2C_{n}^2C_{n}^1C_{n}^1+6C_{n}^2C_{n}^1C_{n}^1C_{n}^1C_{n}^1\)
a(n)=0, 152, 3084, 22404, 98900, 324516, 874104, 2044952, 4304088, 8343360, 15142292, 26038716, 42807180, 67745132, 103766880, ...

mathe

取n=m为素数，那么我们知道总共一直一种选择1+2+...+m是符合条件的方和，
而公式给出总数为\(\lceil\frac5m\rceil\),所以对于m=3不成立，但是对于$m\ge 5$成立。

同样如果我们选择n=m+1,那么总共只有两种选择1+2+...+m和2+3+...+m+(m+1)都满足和是素数m的倍数。
而公式给出总数为\(\lceil\frac{m+5}m\rceil\),所以同样对于$m\ge5$成立。

mathe

但是如果n=m+2时，由于n个数总和模m为3，我们需要去掉两个和模m为3的数。
对于m的所有余数，要求和等于3将m组数两两分组，分成\(\frac{m-1}2\)组，其中\(\frac{m+3}2\)无法归入任何一组。
模1和2分在同一组。淘汰1+2组形式的组合有4总，而淘汰其他组都只有一种，所以总共\(4+\frac{m-3}2=\frac{m+5}2\)。
而公式在$m\ge5$时，给出\(\lceil\frac{m^2+3m+10}{2m}\rceil\),显然对于m充分大时是不对的。

王守恩

TSC999 发表于 2021-8-3 20:13
今天折腾出了 \(m=2、4、6、8 \) 的公式如下：\[
F(n,2)=C_n^2/2-\lfloor{n/2}\rfloor/2 \quad .......... ...

在 1～n 中任意取 9 个不同整数，使得这 9 个数之和能被 9 整除，有几种不同取法？

\(a(n)=\frac{n!/9}{9!(n-9)!}-\frac{2\lfloor n/9\rfloor^5-20\lfloor n/9\rfloor^4+43\lfloor n/9\rfloor^3}{27}\)
\(+(\frac{73\lfloor n/9\rfloor^2-24\lfloor n/9\rfloor\ \ }{27})(\lfloor\frac{(n+8)_{9}+1}{9}\rfloor+\lfloor\frac{(n+7)_{9}+1}{9}\rfloor+\lfloor\frac{(n+6)_{9}+1}{9}\rfloor)\)
\(+(\frac{100\lfloor n/9\rfloor^2-33\lfloor n/9\rfloor\ \ }{27})(\lfloor\frac{(n+5)_{9}+1}{9}\rfloor+\lfloor\frac{(n+4)_{9}+1}{9}\rfloor+\lfloor\frac{(n+3)_{9}+1}{9}\rfloor)\)
\(+(\frac{127\lfloor n/9\rfloor^2-24\lfloor n/9\rfloor\ \ }{27})(\lfloor\frac{(n+2)_{9}+1}{9}\rfloor+\lfloor\frac{(n+1)_{9}+1}{9}\rfloor+\lfloor\frac{(n)_{9}+1}{9}\rfloor)\)
{0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 26, 81, 224, 559, 1274, 2704, 5408, 10270, 18668,
32668, 55278, 90808, 145292, 227011, 347186, 520779, 767454, 1112799, 1589712,
2240037, 3116562, 4285272, 5827956, 7845312, 10460416,13822676,18112456,23546192,}
注：《整数序列在线百科全书(OEIS)》没有收录。

补充内容 (2021-8-7 19:27):
公式不对！光凭前面2,3,4,6,8的规律，还是推不出9的规律来。n=39,42,45,...还得来几项。

补充内容 (2021-8-15 11:13):

请删除! 这个公式不对！12楼的公式才是对的。
这个公式好像哪里还不对