组合数的质因子次数

（写作于 2025-12-28；更新于 2026-01-01）

对于命题 $𝑃$ ，记 $[𝑃] = {\begin{cases} 1, & 𝑃 \\ 0, & \neg 𝑃 \end{cases}$ 。

对于质数 $𝑝$ ，用 $𝜈_{𝑝} (𝑛)$ 为 $𝑛$ 的质因子分解中 $𝑝$ 的次数， $𝜎_{𝑝} (𝑛)$ 表示 $𝑛$ 在 $𝑝$ 进制下的数字和。

定理一：设 $𝑛 \in ℕ$ ， $𝑝$ 是质数，则

𝜈_{𝑝} (𝑛!) = \sum_{𝑘 = 1}^{\infty} ⌊ \frac{𝑛}{𝑝^{𝑘}} ⌋ = \frac{𝑛 - 𝜎_{𝑝} (𝑛)}{𝑝 - 1}

证明：

设 $𝑛 = \sum_{𝑘 = 0}^{\infty} 𝑛_{𝑘} 𝑝^{𝑘}$ ，其中 $𝑛_{𝑘} \in ℕ, 𝑛_{𝑘} < 𝑝$ ，则

\begin{aligned} 𝜈_{𝑝} (𝑛!) \\ = & \sum_{𝑘 = 1}^{𝑛} 𝜈_{𝑝} (𝑘) \\ = & \sum_{𝑘 = 1}^{𝑛} \sum_{𝑗 = 1}^{\infty} [𝑝^{𝑗} ∣ 𝑘] \\ = & \sum_{𝑗 = 1}^{\infty} \sum_{𝑘 = 1}^{𝑛} [𝑝^{𝑗} ∣ 𝑘] \\ = & \sum_{𝑗 = 1}^{\infty} ⌊ \frac{𝑛}{𝑝^{𝑗}} ⌋ \\ = & \sum_{𝑗 = 1}^{\infty} \sum_{𝑖 = 𝑗}^{\infty} 𝑛_{𝑖} 𝑝^{𝑖 - 𝑗} \\ = & \sum_{𝑖 = 0}^{\infty} \sum_{𝑗 = 1}^{𝑖} 𝑛_{𝑖} 𝑝^{𝑖 - 𝑗} \\ = & \sum_{𝑖 = 0}^{\infty} 𝑛_{𝑖} \sum_{𝑗 = 1}^{𝑖} 𝑝^{𝑖 - 𝑗} \\ = & \sum_{𝑖 = 0}^{\infty} 𝑛_{𝑖} \frac{𝑝^{𝑖} - 1}{𝑝 - 1} \\ = & \frac{1}{𝑝 - 1} \sum_{𝑖 = 0}^{\infty} 𝑛_{𝑖} (𝑝^{𝑖} - 1) \\ = & \frac{1}{𝑝 - 1} (\sum_{𝑖 = 0}^{\infty} 𝑛_{𝑖} 𝑝^{𝑖} - \sum_{𝑖 = 0}^{\infty} 𝑛_{𝑖}) \\ = & \frac{𝑛 - 𝜎_{𝑝} (𝑛)}{𝑝 - 1} \end{aligned}

定理一得证。

定理二：设 $𝑛 \in ℕ, 𝑚 \in ℕ$ ， $𝑝$ 是质数，则

𝜈_{𝑝} (𝐶_{𝑛 + 𝑚}^{𝑛}) = \sum_{𝑘 = 1}^{\infty} [𝑛 mod 𝑝^{𝑘} + 𝑚 mod 𝑝^{𝑘} \geq 𝑝^{𝑘}]

证明：

\begin{aligned} 𝜈_{𝑝} (𝐶_{𝑛 + 𝑚}^{𝑛}) \\ = & 𝜈_{𝑝} (\frac{(𝑛 + 𝑚)!}{𝑛! 𝑚!}) \\ = & 𝜈_{𝑝} ((𝑛 + 𝑚)!) - 𝜈_{𝑝} (𝑛!) - 𝜈_{𝑝} (𝑚!) \\ = & \sum_{𝑘 = 1}^{\infty} (⌊ \frac{𝑛 + 𝑚}{𝑝^{𝑘}} ⌋ - ⌊ \frac{𝑛}{𝑝^{𝑘}} ⌋ - ⌊ \frac{𝑚}{𝑝^{𝑘}} ⌋) \\ = & \sum_{𝑘 = 1}^{\infty} (\frac{𝑛 + 𝑚 - (𝑛 + 𝑚) mod 𝑝^{𝑘}}{𝑝^{𝑘}} - \frac{𝑛 - 𝑛 mod 𝑝^{𝑘}}{𝑝^{𝑘}} - \frac{𝑚 - 𝑚 mod 𝑝^{𝑘}}{𝑝^{𝑘}}) \\ = & \sum_{𝑘 = 1}^{\infty} \frac{𝑛 mod 𝑝^{𝑘} + 𝑚 mod 𝑝^{𝑘} - (𝑛 + 𝑚) mod 𝑝^{𝑘}}{𝑝^{𝑘}} \\ = & \sum_{𝑘 = 1}^{\infty} ⌊ \frac{𝑛 mod 𝑝^{𝑘} + 𝑚 mod 𝑝^{𝑘}}{𝑝^{𝑘}} ⌋ \\ = & \sum_{𝑘 = 1}^{\infty} [𝑛 mod 𝑝^{𝑘} + 𝑚 mod 𝑝^{𝑘} \geq 𝑝^{𝑘}] \end{aligned}

其中，最后一行是因为 $0 \leq 𝑛 mod 𝑝^{𝑘} + 𝑚 mod 𝑝^{𝑘} < 2 𝑝^{𝑘}$ 。定理二得证。

由于在 $𝑝$ 进制下计算 $𝑛 + 𝑚$ 时，从右到左第 $𝑘$ 位有进位当且仅当 $𝑛 mod 𝑝^{𝑘} + 𝑚 mod 𝑝^{𝑘} \geq 𝑝^{𝑘}$ ，我们有

推论： $𝜈_{𝑝} (𝐶_{𝑛 + 𝑚}^{𝑛})$ 等于在 $𝑝$ 进制下计算 $𝑛 + 𝑚$ 时进位的次数。