小粉兔介绍了一种 Lucas 定理的超级简洁形象的证明,至少是我见过的最简洁的证明。
前置知识:二项式定理。
所用的特殊记号:艾弗森括号、系数提取符/系数算子。
Lucas 定理内容:
其中 \(P\) 是质数。
首先我们需要一个结论:
证明:
通过二项式定理拆分左半边:
展开组合数:
把 \((P - 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\)
所以:
(此处中括号表示“艾弗森括号”,即中括号内为真时值为 \(1\) 否则为 \(0\))
也就是说:
证毕。
然后正式开始证明 Lucas 定理。
首先使用二项式定理,把所求组合数转化为二项式系数:
(此处中括号表示“系数提取符/系数算子”,即表示 \((1 + x)^n\) 中 \(x^m\) 项的系数)
右侧指数可以通过小学除法知识拆分:
设 \(k = \lfloor \frac{n}{P} \rfloor\),\(r = n \bmod P\),然后单独看右边被提取系数的式子:
(最后一步用了刚才所证明的结论)
我们把右侧需要提取系数的那个式子单独拿出来,用二项式定理展开:
回到刚才的问题,我们要求这个式子的 \(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}\)
综上所述:
根据定义,\(k = \lfloor \frac{n}{P} \rfloor\),\(r = n \bmod P\),所以:
证毕。