当前位置: 首页 > news >正文

2025.9.24 闲话:Lucas 定理究极证明

小粉兔介绍了一种 Lucas 定理的超级简洁形象的证明,至少是我见过的最简洁的证明。

前置知识:二项式定理。

所用的特殊记号:艾弗森括号、系数提取符/系数算子。

Lucas 定理内容:

\[\binom{n}{m} \equiv \binom{\lfloor n \div P \rfloor}{\lfloor m \div P \rfloor} \binom{n \bmod P}{m \bmod P} \pmod{P} \]

其中 \(P\) 是质数。


首先我们需要一个结论:

\[(1 + x)^{P} \equiv 1 + x^{P} \pmod{P} \]

证明:

通过二项式定理拆分左半边:

\[(1 + x)^{P} = \sum_{i = 0}^{P} \binom{P}{i} x^{i} \]

展开组合数:

\[\binom{P}{i} = \frac{P!}{i! (P - i)!} \]

\((P - i)!\) 除上去:

\[\frac{P!}{i! (P - i)!} = \frac{P (P - 1) \dots (P - i + 1)}{i!} \]

因为 \(P\) 是质数,所以(当 \(i \neq 0\) 时)分子上的 \(P\) 不会被除了 \(1\)\(P\) 以外的正整数整除。

  • 如果 \(i = 0\),此时分母上的 \(P\) 项根本不存在,\(\binom{P}{i} = \binom{P}{0} = 1\)

  • 如果 \(0 < i < P\),那么分母上的乘积必然不会出现 \(P\) 因子,分子的 \(P\) 也不会被消去,此时原式被 \(P\) 整除

  • 如果 \(i = P\),那么 \(\binom{P}{i} = \binom{P}{P} = 1\)

所以:

\[\binom{P}{i} \equiv [(i = 0) \parallel (i = P)] \pmod{P} \]

(此处中括号表示“艾弗森括号”,即中括号内为真时值为 \(1\) 否则为 \(0\)

也就是说:

\[\begin{aligned} \sum_{i = 0}^{P} \binom{P}{i} x^{i} &\equiv \sum_{i = 0}^{P} [(i = 0) \parallel (i = P)] x^{i} \\ &\equiv x^0 + x^P \\ (1 + x)^{P} &\equiv 1 + x^{P} \pmod{P} \end{aligned} \]

证毕。


然后正式开始证明 Lucas 定理。

首先使用二项式定理,把所求组合数转化为二项式系数:

\[\binom{n}{m} = [x^m](1 + x)^{n} \]

(此处中括号表示“系数提取符/系数算子”,即表示 \((1 + x)^n\)\(x^m\) 项的系数)

右侧指数可以通过小学除法知识拆分:

\[\begin{aligned} \binom{n}{m} &= [x^m](1 + x)^{n} \\ &= [x^m](1 + x)^{ (P \times \lfloor \frac{n}{P} \rfloor) + (n \bmod P) } \\ \end{aligned} \]

\(k = \lfloor \frac{n}{P} \rfloor\)\(r = n \bmod P\),然后单独看右边被提取系数的式子:

\[\begin{aligned} (1 + x)^{ kP + r } &= (1 + x)^{ kP + r } \\ &= (1 + x)^{kP} \times (1 + x)^r \\ &= \left( (1 + x)^P \right)^k \times (1 + x)^r \\ &\equiv (1 + x^P)^k \times (1 + x)^r \pmod{P} \end{aligned} \]

(最后一步用了刚才所证明的结论)

我们把右侧需要提取系数的那个式子单独拿出来,用二项式定理展开:

\[\begin{aligned} (1 + x^P)^{k} \times (1 + x)^r &= \left( \sum_{i = 0}^{k} \binom{k}{i} x^{iP} \right) \left( \sum_{i = 0}^{r} \binom{r}{i}x^i \right) \\ &= \sum_{i = 0}^{k} \sum_{j = 0}^{r} \left( \binom{k}{i} x^{iP} \times \binom{r}{j} x^j \right) \\ &= \sum_{i = 0}^{k} \sum_{j = 0}^{r} \left( \binom{k}{i} \binom{r}{j} x^{iP + j} \right) \end{aligned} \]

回到刚才的问题,我们要求这个式子的 \(x^m\) 项的系数。

上述求和项的指数可以列成表格:

\(i \backslash j\) \(0\) \(1\) \(\cdots\) \(r\)
\(0\) \(0\) \(1\) \(\cdots\) \(r\)
\(1\) \(P\) \(P + 1\) \(\cdots\) \(P + r\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\)
\(k\) \(kP\) \(kP + 1\) \(\cdots\) \(kP +r\)

我们发现,\(j \le r = (n \bmod P) < P\),所以 \(iP + j < (i + 1) P\),因此每一行最右侧的数也要比下一行最左侧的数要小。

又因为每一行内部是递增的,所以如果按照外层枚举行,内层枚举列的顺序,整个表格也是单调递增的。

因此表格内的数字两两不重复。所以,\(m\) 在上面表格中出现的次数至多有 \(1\) 次,也就是说 \(x^m\) 的出现次数在原式中也至多有 \(1\) 次。

找到这一次所对应的 \(i, j\) 是容易的。因为 \(iP + j = m\),所以 \(i = \lfloor m \div P \rfloor, j = m \bmod P\)

  • \(j \le r\) 时,这一项在原式中存在,其系数就是 \(\binom{k}{i} \binom{r}{j}\)

  • \(j > r\) 是,这一项在原式中不存在,其系数为 \(0\)。但是因为此时 \(\binom{r}{j} = 0\)(我们定义当 \(x < y\)\(\binom{x}{y} = 0\)),所以依然可以说其系数为 \(\binom{k}{i} \binom{r}{j}\)

综上所述:

\[\begin{aligned} \binom{n}{m} &= [x^m](1 + x)^{n} \\ &\equiv [x^m] \left( \sum_{i = 0}^{k} \sum_{j = 0}^{r} \left( \binom{k}{i} \binom{r}{j} x^{iP + j} \right) \right) \\ &\equiv \binom{k}{\lfloor m \div P \rfloor} \binom{r}{m \bmod P} \pmod{P} \end{aligned} \]

根据定义,\(k = \lfloor \frac{n}{P} \rfloor\)\(r = n \bmod P\),所以:

\[\binom{n}{m} \equiv \binom{\lfloor n \div P \rfloor}{\lfloor m \div P \rfloor} \binom{n \bmod P}{m \bmod P} \pmod{P} \]

证毕。

http://www.hskmm.com/?act=detail&tid=16133

相关文章:

  • Are English people good or bad
  • 9
  • Lampiao靶场渗透wp-脏牛提权
  • 画矩形
  • NOIP 模拟赛八
  • 第三篇
  • 基于cloacked-pixel隐写工具爆破项目
  • 随便写的
  • Bcliux-docker-nacos2.2.0升级至2.2.3版本
  • 社交网络架构。京东场景题:亿级用户100Wqps 社交关系如何设计?如何查看我的关注,关注我的?
  • go 面试题
  • 事件和图形界面(暂未完成)
  • 什么是sql 慢日志。哈罗面试:没开sql慢日志,怎么发现慢 sql?
  • Spring连环炮。哈罗面试:Spring Bean生命周期,Spring怎么创建Bean的,BFPP和BPP的x别
  • redis 大 key 优化。哈罗面试:redis 有个大 key需要在线优化, 不能影响现有业务,请求不能大量到库,怎么优化?
  • ACL高可用架构。希音面试:第三方挂了,我们总在背锅。来一 靠谱的 高可用方案,让 外部依赖 稳如泰山
  • 软工9.24
  • 2025CSP-S模拟赛51
  • 2025年9月24日 - 20243867孙堃2405
  • 【星海随笔】RabbitMQ开发篇 - 教程
  • P13754 【MX-X17-T3】Distraction
  • 2025.9.24
  • 初学汇编
  • 架构图设计还得是华为 - 智慧园区
  • 解决zsh: corrupt history file /home/sgud4h5gh/.zsh_history的办法
  • StarRocks GitHub 工作流程
  • 对象初始化器的使用方法
  • C++、Java 和 Python 在输入输出差别
  • 我的学习记录之自我介绍、思维导图和监督措施
  • 用 Java 和 Tesseract 进行验证码识别:基础实现与优化