数学研发论坛

 找回密码
 欢迎注册
查看: 2511|回复: 82

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

[复制链接]
发表于 2021-7-31 16:47:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
{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 证明是有错的,这个错误是我的,不是陆教授的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-7-31 17:14:46 | 显示全部楼层
下面是一个验证公式的 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
搜索结果与公式计算值一致。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-1 08:40:12 | 显示全部楼层
对于 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}

点评

公式①与公式②不一样:m=7,n=28,29,...,m=11,n=22,23,...,m=13,n=26,27,...  发表于 2021-8-5 15:41
这里的大侠们都没有参与其中进行讨论。  发表于 2021-8-1 22:36
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-1 18:21:57 | 显示全部楼层
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函数可以直接扫描表。

点评

谢谢 chyanog!从您这里还真是学了不少!谢谢 chyanog!  发表于 2021-8-15 13:25
Table[Total[1-Unitize[Mod[Total/@Subsets[Range@n,{9}],9]]],{n,9,25}] 这样写更快一些  发表于 2021-8-14 18:42
还是没搞懂:Count[Total/@Subsets[Range@n,{m}],_Integer]=n!/(m!(n-m)!)  发表于 2021-8-9 18:55
太好了!还有这么简单的:Count[Total/@Subsets[Range@n,{m}]/m,_Integer]  发表于 2021-8-5 11:26
更进一步,Mathematica是这么玩的:Count[Total/@Subsets[Range@n,{m}]/m,_Integer]  发表于 2021-8-5 09:16
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-3 20:13:16 | 显示全部楼层
今天折腾出了 \(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}\]
能否将这些按余数分段的公式合并、统一成一个简单公式?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-4 09:44:44 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-4 19:38 编辑

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-5 11:12:17 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-5 11:22 编辑
王守恩 发表于 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, ...
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-5 12:34:40 | 显示全部楼层
取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$成立。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-5 12:45:01 | 显示全部楼层
但是如果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充分大时是不对的。

点评

是对的吧。  发表于 2021-8-5 18:25
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-6 17:31:34 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-6 18:02 编辑
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楼的公式才是对的。
这个公式好像哪里还不对

点评

这个公式好像哪里还不对。因为当 n = 9 ~44 时计算结果都是整数,但是当 n 大于等于 45 时计算结果非整数。  发表于 2021-8-7 08:56
经验证,这个 m = 9 的公式完全正确!  发表于 2021-8-7 08:35
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-9-26 15:35 , Processed in 0.089679 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表