生成函数与卢卡斯定理

Generating Functions

** Definition. ** A generating function is a power series $f(x) = \sum_{n = 0}^\infty a_nx^n$.

Lucas' Theorem

** Definition. ** Let $n = (n_l n_{l - 1} \dots n_0)_p$ be the base $p$ representation of $n$. That is, $n = \sum_{i = 0}^l n_i p^i$.

** Theorem. ** Lucas' Theorem states that if $n = (n_l n_{l-1} \dots n_0)_p$ and $k = (k_l k_{l-1} \dots k_0)_p$ (for some appropriate value of $l$) then $\binom{n}{k} \equiv_p \prod_{i = 0}^l \binom{n_i}{k_i}$.

Proof of Lucas' Theorem

Let $n = (n_l n_{l-1} \dots n_0)_p$ and $k = (k_l k_{l-1} \dots k_0)_p$ denote the base $p$ representations of $n, k$.

** Definition. ** Let $f(x)$ be a generating function. Then $[x^n]f(x)$ denotes the coefficient of $x^n$ in $f(x)$.

We then have the following: \begin{align*} \binom{n}{k} &= [x^k](1 + x)^n & \text{By the Binomial Theorem}\ &= [x^k] (1 + x)^{n_0 + n_1 p + n_2 p^2 + \dots + n_l p^l}\ &= [x^k]\prod_{i = 0}^l [(1 + x)^{n_i p^i}]\ &= [x^k]\prod_{i = 0}^l [(1 + x)^{p^i}]^{n^i}\ &\equiv_p [x^k] \prod_{i = 0}^l (1 + x^{p^i})^{n^i} & \text{By expanding $(x+1)^{p^i}$ modulo $p$}\ &= [x^k]\prod_{i = 0}^l \sum_{j_i = 0}^{n_i} \binom{n_i}{j_i}(x^{p^i})^{j_i} & \text{By the Binomial Theorem}\ &= [x^k]\prod_{i = 0}^l \sum_{j_i = 0}^{n_i} \binom{n_i}{j_i}(x^{j_ip^i}) \end{align*}

Now this looks pretty ugly, but it'll work out. Since we are only concerned with the coefficients of $x^k$, the only term that matters from the $i$th product term is $\binom{n_i}{k_i} (x^{k^i p^i})$, since the representation of $k$ in base $p$ is unique. It then follows that $[x^k]\prod_{i = 0}^l \sum_{j_i = 0}^{n_i} \binom{n_i}{j_i}(x^{j_i p^i})= \prod_{i = 0}^l \binom{n_i}{k_i}$ as desired.