十二重 GF 法

· · 题解

写一篇纯 GF 题解！

I

一个盒子是 \mathrm e^z，则

\left[\frac{z^n}{n!}\right] \mathrm e^{mz} = m^n

II

一个盒子是 1+z，则

\left[\frac{z^n}{n!}\right] (1+z)^m = n! \binom mn = m^{\underline n}

III

一个盒子是 \mathrm e^z - 1，则

\begin{aligned} \left[\frac{z^n}{n!}\right] (\mathrm e^z-1)^m &= \left[\frac{z^n}{n!}\right] \sum\limits_{k=0}^m \binom mk \mathrm e^{kz} (-1)^{m-k} \\ &= \sum\limits_{k=0}^m \binom mk k^n (-1)^{m-k} \end{aligned}

IV

所有空盒不可区分，而所有非空盒事实上被盒中的球的标号区分，则

\begin{aligned} \left[\frac{z^n}{n!}\right] \sum\limits_{k=0}^m \frac1{k!}(\mathrm e^z-1)^k &= \left[\frac{z^n}{n!}\right] \sum\limits_{k=0}^m \frac1{k!} \sum\limits_{i=0}^k \binom ki \mathrm e^{iz} (-1)^{k-i} \\ &= \left[\frac{z^n}{n!}\right] \sum\limits_{i=0}^m \frac{\mathrm e^{iz}}{i!} \sum\limits_{k=i}^m \frac{(-1)^{k-i}}{(k-i)!} \\ &= \sum\limits_{i=0}^m \frac{i^n}{i!} \sum\limits_{k=0}^{m-i} \frac{(-1)^k}{k!} \end{aligned}

V

\left[\frac{z^n}{n!}\right] \sum\limits_{k=0}^m \frac1{k!}z^k = [n\le m]

VI

\begin{aligned} \left[\frac{z^n}{n!}\right] \frac1{m!}(\mathrm e^z-1)^m &= \left[\frac{z^n}{n!}\right] \frac1{m!}\sum\limits_{k=0}^m \binom mk \mathrm e^{kz} (-1)^{m-k} \\ &= \frac1{m!}\sum\limits_{k=0}^m \binom mk k^n (-1)^{m-k} \end{aligned}

VII

一个盒子是 \frac1{1-z}，则

[z^n] \frac1{(1-z)^m} = \binom{n+m-1}n

VIII

一个盒子是 1+z，则

[z^n] (1+z)^m = \binom mn

IX

一个盒子是 \frac z{1-z}，则

[z^n] \frac{z^m}{(1-z)^m} = \binom{n-1}{m-1}

X

令二元 GF

F(z,q) = \prod\limits_{k\ge 0} \frac1{1-qz^k}

那么

F(z,q) = \frac1{1-q} F(z,qz)

令 F_m(z) = [q^m] F(z,q)，则

F_m(z) = \frac1{1-z^m} F_{m-1}(z)

由于 F_0(z)=1，则

F_m(z) = \prod\limits_{k=1}^m \frac1{1-z^k}

故答案为

[z^n] F_m(z)

而

\begin{aligned} F_m(z) &= \prod\limits_{k=1}^m \frac1{1-z^k} \\ &= \exp\left[\sum\limits_{k=1}^m \ln \frac1{1-z^k}\right] \\ &= \exp\left[\sum\limits_{k=1}^m \sum\limits_{i\ge 1} \frac{z^{ki}}i\right] \end{aligned}

XI

令二元 GF

F(z,q) = \frac1{1-q}\frac1{1-qz}

则

[z^n q^m] F(z,q) = [n\le m]

XII

令二元 GF

F(z,q) = \prod\limits_{k\ge 1} \frac1{1-qz^k}

那么

F(z,q) = \frac1{1-qz} F(z,qz)

令 F_m(z) = [q^m] F(z,q)，则

F_m(z) = \frac z{1-z^m} F_{m-1}(z)

由于 F_0(z)=1，则

F_m(z) = \prod\limits_{k=1}^m \frac z{1-z^k}

故答案为

[z^n] F_m(z)

而

\begin{aligned} F_m(z) &= \prod\limits_{k=1}^m \frac z{1-z^k} \\ &= z^m \exp\left[\sum\limits_{k=1}^m \ln \frac1{1-z^k}\right] \\ &= z^m \exp\left[\sum\limits_{k=1}^m \sum\limits_{i\ge 1} \frac{z^{ki}}i\right] \end{aligned}