免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 关于组合数被素数整除

由这帖 http://kuing.orzweb.net/redirect ... =5794&pid=29242(18楼)的方法可以看出,要判断组合数能否被某数整除以及个数的统计,如果数比较大一般挺麻烦,主要与被除数的质因数分解的复杂度有关。

而如果被除数只是一个素数,那就简单多了,下面来写写,以下如无特别说明,所有字母均默认为自然数,另外统一设 `k\leqslant n`。

问题:设 `a` 为素数,判断 `C_n^k` 能否被 `a` 整除。

解:设 `n` 的 `a` 进制表达式为
\[n=n_0+n_1a+n_2a^2+\cdots+n_sa^s=(n_s\cdots n_1n_0)_a,\]
仿照链接中的方法,`C_n^k=\frac{n!}{k!(n-k!)}`,设其分子和分母的质因数分解中 `a` 的次数分别为 `N_a` 和 `M_a`,则
\begin{align*}
N_a&=\left[ \frac na \right]+\left[ \frac n{a^2} \right]+\cdots+\left[ \frac n{a^s} \right],\\
M_a&=\left[ \frac ka \right]+\left[ \frac{n-k}a \right]+\left[ \frac k{a^2} \right]+\left[ \frac{n-k}{a^2} \right]+\cdots+\left[ \frac k{a^s} \right]+\left[ \frac{n-k}{a^s} \right],
\end{align*}
得到 `C_n^k` 的质因数分解中 `a` 的次数为
\[N_a-M_a=d_1+d_2+\cdots+d_s,\]
其中
\[d_i=\left[ \frac n{a^i} \right]-\left[ \frac k{a^i} \right]-\left[ \frac{n-k}{a^i} \right]=-\left[ \frac{(n\bmod a^i)-(k\bmod a^i)}{a^i} \right],\]
那么,`C_n^k` 不能被 `a` 整除等价于 `N_a-M_a=0`,即所有 `d_i` 都为零,亦即
\[k\bmod a^i\leqslant n\bmod a^i\]
对 `1\leqslant i\leqslant s` 都成立,易知这也等价于 `k` 的 `a` 进制表达式中的每一位数都不大于 `n` 的对应位上的数,也就是:

定理:设 `a` 为素数,`k`, `n` 的 `a` 进制表达式分别为 `n=(n_s\cdots n_1n_0)_a`, `k=(k_s\cdots k_1k_0)_a`,则若 `k_i\leqslant n_i` 对 `0\leqslant i\leqslant s` 都成立,则 `C_n^k` 不能被 `a` 整除,否则就能整除。

(注:实际当中 `k` 的位数可以小于 `n` 的位数,但定理这样写也是没问题的,因为可以视作 `k` 的前若干位为零。)

由 `k_i\leqslant n_i` 知 `k_i` 有 `n_i+1` 种选择,所以有:

推论:设 `a` 为素数,给定 `n` 的 `a` 进制表达式为 `(n_s\cdots n_1n_0)_a`,则使 `C_n^k` 不能被 `a` 整除的 `k` 共 `(n_0+1)(n_1+1)\cdots(n_s+1)` 个。

OK,现在来试用一下。
例 1:
(1)判断 `C_{2018}^{123}` 和 `C_{2018}^{1234}` 能否被 `7` 整除;
(2)求 `C_{2018}^k`(`0\leqslant k\leqslant2018`)中不能被 `7` 整除的个数。
解:因为
\begin{alignat*}{2}
2018={} && 5612_7\\
123={} && 234_7\\
1234={} && 3412_7
\end{alignat*}
由定理得:(1)`C_{2018}^{123}` 能被 `7` 整除,`C_{2018}^{1234}` 不能被 `7` 整除;
由推论得:(2)共 `(5+1)(6+1)(1+1)(2+1)=252` 个。

此例的结果用程序验证通过。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
$\href{https://kuingggg.github.io/}{\text{About Me}}$

当年这帖 http://kuing.orzweb.net/redirect ... tid=163&pid=859 所引用的奇偶判定准则及后面的个数推论与上面的结论应该是没有矛盾的吧?

TOP

回复 2# kuing


    我只是从表面上看,进制的推广,应该是统一和和谐的

TOP

回复 3# isee

现在已经可以肯定和那个是没矛盾的:
如果 m 和 n-m 的二进制没有同一位为 1,那在两者相加时就不会出现进位,所以 n 的每一位必然都不小于 m 的;
而如果存在同一位为 1,同最后一对 1 相加时就会变成 0,所以 n 的该位就会小于 m 的。
综上可知链接中的奇偶判定准则与 1# 的结论相容。

TOP

https://artofproblemsolving.com/ ... _10__64_pascal_rows

剛剛在這裡解決了相關的題目,先把重點結論搬過來

n的2進制表達式為$(n_s\dots n_1 n_0)_2$,則使$C_n^k$不能被2整除的k共$2^{n_0+n_1+\dots+n_s}$

n的2進制表達式為$(n_s\dots n_1 n_0)_2$,且使$n_m=0,n_{m+1}=1$成立的m有K個,則使$C_n^k$能被2整除但不能被4整除的k共$2^{n_0+n_1+\dots+n_s-1} K$

TOP

https://artofproblemsolving.com/ ... ascals_triangle_row

這裡分析了不同的m使$v_p\left(\binom{n}{m}\right)=0,1$

TOP

返回列表 回复 发帖