文章目錄

• 有用的式子
• • 1.（牛頓二項式定理）
  • 2.
• 普通生成函數(shù)（OGF）
• • 常見封閉形式：
  • 1.
  • 2.
  • 3.
  • 4.
• 指數(shù)生成函數(shù)（EGF）
• • 排列與圓排列

有用的式子

1.（牛頓二項式定理）

我們把組合數(shù)的定義推廣：
$$\left(\genfrac{}{}{0ex}{}{r}{k}\right)=\frac{r^{\underline{k}}}{k!}(r\in \mathbf{C},k\in \mathbf{N})$$
其中 $r^{\underline{k}}$ 指下降冪，即 ${\prod }_{i=0}^{k?1}(r?i)$。（不過大多數(shù)時候我們只需要用到實數(shù)域的定義）
然后我們就可以對二項式定理進行推廣：
$$(1+x{)}^r=\sum _{i\ge 0}(\genfrac{}{}{0ex}{}{r}{i})x^i(r\in \mathbf{C})$$

2.

對于組合數(shù)：
$$\left(\genfrac{}{}{0ex}{}{n+m}{m}\right)$$
我們考慮其實際意義，枚舉其與最右側(cè)相連的極長連續(xù)段長度 $i$，那么就有：
$$\left(\genfrac{}{}{0ex}{}{n+m}{m}\right)=\sum _{i=0}^m\left(\genfrac{}{}{0ex}{}{n+m?i?1}{m?i}\right)=\sum _{i=0}^m\left(\genfrac{}{}{0ex}{}{n+i?1}{i}\right)$$
我們常常會用到這個式子的反演。

普通生成函數(shù)（OGF）

數(shù)列 $a$ 的普通生成函數(shù)為：
$$F(x)=\sum _{n=0}{a}_n{x}_n$$
卷積性質(zhì)：
$$A(x)?B(x)=\sum _{n=0}{x}^n\sum _{i=0}^n{a}_i{b}_{n?i}$$

常見封閉形式：

1.

$$\sum _{n=0}{x}^n=\frac{1}{1?x}$$
$$\sum _{n=0}^k{x}^n=\frac{1?x^{k+1}}{1?x}$$
證明：
就是等比求和公式。

2.

$$\sum _{n=0}\left(\genfrac{}{}{0ex}{}{n+k?1}{k?1}\right)x^n=\frac{1}{(1?x{)}^k}$$
證明：

數(shù)學歸納法：結(jié)合式子一大力揉式子。

隔板法：第 $n$ 項的系數(shù)等同于從 $k$ 個 ${\sum }_{n=0}{x}^n$ 中個選出一項，次數(shù)后恰好為 $n$ 的方案數(shù)，那么就轉(zhuǎn)換為 $k$ 個有序非負整數(shù)加和為 $n$ 的方案數(shù)。全加一后隔板即可。

3.

$$\sum _{n=0}\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^n=\frac{x^k}{(1?x{)}^{k+1}}$$
證明：
第二個式子，為了方便稍微變下形：
$$\sum _{n=0}\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)x^n=\frac{1}{(1?x{)}^{k+1}}$$
然后兩邊同乘 $x^k$：
$$\sum _{n=0}\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)x^{n+k}=\frac{x^k}{(1?x{)}^{k+1}}$$
$$\sum _{n=k}\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^n=\frac{x^k}{(1?x{)}^{k+1}}$$
由于 $n<k$ 是組合數(shù)全是0，所以求和可以伸下去，得到：
$$\sum _{n=0}\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^n=\frac{x^k}{(1?x{)}^{k+1}}$$

4.

$$\sum _{n=0}\left(\genfrac{}{}{0ex}{}{k}{n}\right)x^n=(1+x{)}^k$$
證明：
二項式定理即可。

指數(shù)生成函數(shù)（EGF）

數(shù)列 $a$ 的指數(shù)生成函數(shù)為：
$$\hat{F}(x)=\sum _{i=0}\frac{a_i}{n!}{x}^i$$
卷積性質(zhì)：
$$\hat{A}(x)?\hat{B}(x)=\sum _{n=0}{x}^n\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)a_i{b}_{n?i}$$

排列與圓排列

排列的方案數(shù)為 $n!$，其 EGF 為：
$$\hat{P}(x)=\sum \frac{n!}{n!}{x}^n=\frac{1}{1?x}$$
類似于組合數(shù)的證明，每個圓排列對應 $n$ 個排列，方案數(shù)為 $(n?1)!$，其 EGF 為：
$$\hat{Q}(x)=\sum \frac{(n?1)!}{n!}{x}^n=\sum \frac{x^n}{n}=?\ln (1?x)=\ln \frac{1}{1?x}=\ln \hat{P}(x)$$
（$\sum \frac{x^n}{n}=?\ln (1?x)$ 可通過對兩邊求導再積分證明）
這個關系可以這么理解：每個排列可以形成若干個置換環(huán)，每個置換環(huán)都是一個圓排列問題。
所以 當一個問題 $F$ 可以轉(zhuǎn)化為按照任意方法分成若干集合，每種劃分的貢獻是每個集合 $G$ 問題的方案累乘起來時，它們的 EGF 就有如下等量關系：
$$\hat{F}(x)=\exp (\hat{G}(x))$$

總結(jié)

以上是生活随笔為你收集整理的生成函数全家桶的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。