最后更新: 2025-01-22 09:06 查看: 65 次反馈刷题

指数型生成函数

定义 7.2 设 $a_1, a_2, \cdots, a_n, \cdots$ 是一个数列，构造形式幂级数

$$
f(x)=\sum_{r=0}^{\infty} \frac{a_r}{r!} x^r=a_0+a_1 x+\frac{a_2}{2!} x^2+\cdots+\frac{a_n}{n!} x^n+\cdots
$$

称 $f(x)$ 是数列 $a_1, a_2, \cdots, a_n, \cdots$ 的指数型生成函数。
根据定义知，指数型生成函数与幂级数型生成函数的一般项仅相差一个因子 $1 / n!$ 。只要令 $a_r^{\prime}=a_r / r!$ ，则 $\left\{a_r^{\prime}\right\}$ 的幂级数型生成函数就是 $\left\{a_r\right\}$ 的指数型生成函数，因此由定理 7.1 易得指数型生成函数的性质。

定理 7.2 设 $\left\{a_n\right\},\left\{b_n\right\}$ 的指数生成函数分别为 $f_e(x)$ 和 $g_e(x)$ ，则

$$
f_e(x) \llbracket g_e(x)=\sum_{n=0}^{\infty} C_n \frac{x^n}{n!}
$$

其中

$$
C_n=\sum_{k=0}^n C(n, k) a_n b_{n-k}
$$

证明留作习题。
对于 $a_n=1$ 的数列 $\{1\}$ ，它的指数型生成函数为

$$
e^x=\sum_{n=0}^{\infty} \frac{x^n}{n!}=1+x+\frac{x^2}{2!}+\cdots+\frac{x^n}{n!}+\cdots
$$

在上节中，用幂级数型生成函数求解多重集的组合问题，而用指数型生成函数则可解决多重集的排列问题。

定理 7.3 设有限多重集 $S=\left\{n_1 \bullet a_1, n_2 \bullet a_2, \cdots, n_k \bullet a_k\right\}$ ，且 $n=n_1+n_2+\cdots+n_k$ ，对任意的非负整数 $r$ ，令 $a_r$ 为 $S$ 的 $r$－排列数，则数列 $\left\{a_r\right\}$ 的指数型生成函数为

$$
g(x)=g_{n_1}(x) \cdot g_{n_2}(x) \cdots g_{n_k}(x)
$$

其中

$$
g_{n_i}(x)=1+x+\frac{x^2}{2!}+\cdots+\frac{x^{n_i}}{n!}, \quad i=1,2 \cdots, \quad k
$$

证明：考察 $g(x)$ 的展开式中 $x^r$ 的项，它必是下述项之和。

$$
\frac{x^{m_1}}{m_{1}!} \cdot \frac{x^{m_2}}{m_{2}!} \cdots \cdot \frac{x^{m_k}}{m_{k}!}
$$

其中 $m_1+m_2+\cdots+m_k=r, 0 \leqslant m_i \leqslant n_i, i=1,2, \cdots, k$ ，而这类项又可写成

$$
\frac{x^{m_{1+m_2+\cdots+m_k}}}{m_{1}!m_{2}!\cdots m_{k}!}=\frac{r!}{m_{1}!m_{2}!\cdots m_{k}!} \cdot \frac{x^r}{r!}
$$

所以在 $g(x)$ 的展开式中 $\frac{x^r}{r!}$ 的系数是

$$
a_r=\sum \frac{r!}{m_{1}!m_{2}!\cdots m_{k}!}
$$

这里求和是对方程

$$
m_1+m_2+\cdots+m_k=r, 0 \leqslant m_i \leqslant n_i(i=1,2, \cdots, k)
$$

的一切非负整数解进行求和的。又因为对固定的 $m_1, m_2, \cdots, m_k, \frac{r!}{m_{1}!m_{2}!\cdots m_{k}!}$ 就是 $S$ 的 $r$ 元子集 $\left\{m_1 \cdot x_1, m_2 \bullet x_2, \cdots, m_{ k } \cdot x_k\right\}$ 的全排列数。故 $a$ 就是 $S$ 的所有 $r$ 元子集的全排列数之和，即 $S$ 的 $r$－排列数。所以 $g(x)$ 的展开式中的 $\frac{x^r}{r!}$ 的系数 $a_r$ 就是多重集 $S$ 的 $r$－排列数。

例7．5 设有 6 个数字，其中有 3 个 $1, ~ 2$ 个 6 和 1 个 8 ，问能组成多少个四位数？
解：这实际上是求 $S=\left\{3 \cdot x_1, 2 \cdot x_2, 1 \cdot x_3\right\}$ 中取 4 个的多重集排列数问题。其指数型生成函数为

$$
\begin{aligned}
& g(x)=\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)\left(1+x+\frac{x^2}{2!}\right)(1+x) \\
& =1+3 x+8 \frac{x^2}{2!}+19 \frac{x^3}{3!}+38 \frac{x^4}{4!}+60 \frac{x^5}{5!}+60 \frac{x^6}{6!}
\end{aligned}
$$

由此可得 $a_4=38$ ，即可组成 38 个四位数。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：幂级数型生成函数

下一篇：递推关系

本文对您是否有用？有用 (0) 无用 (0)