|
|
由这帖 forum.php?mod=redirect&goto=findpost& … d=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` 个。
此例的结果用程序验证通过。 |
|
tommywong
Posted 2018-12-25 21:55
