生成函數(shù)生成果，生成數(shù)下你和我。
生成函數(shù)太美妙，蒟蒻一看被難倒。
$\mathcal{B}y——\mathcal{C}halotto$

---

目錄

• 生成函數(shù)
• • 概念
  • 普通型生成函數(shù)
  • 指數(shù)型生成函數(shù)
  • 例子
  • 經(jīng)典題目
  • • 1、求 Fibonacci 通項(xiàng)公式

---

生成函數(shù)

概念

*度娘定義：

生成函數(shù)又叫 母函數(shù) ( 個(gè)人不太喜歡這個(gè)叫法 )，是組合數(shù)學(xué)中尤其是計(jì)數(shù)方面的一個(gè)重要理論和工具。
生成函數(shù)分為 普通型生成函數(shù) 和 指數(shù)型生成函數(shù) 兩種，前者使用較多。形式上說，普通型生成函數(shù)用于解決多重集的組合問題，而指數(shù)型母函數(shù)用于解決多重集的排列問題。

生成函數(shù)的應(yīng)用簡(jiǎn)單來說在于研究未知（通項(xiàng)）數(shù)列規(guī)律，用這種方法在給出遞推式的情況下求出數(shù)列的通項(xiàng)，生成函數(shù)是推導(dǎo) $Fibonacci$ 數(shù)列的通項(xiàng)公式方法之一，另外組合數(shù)學(xué)中的 $Catalan$ 數(shù)也可以通過生成函數(shù)的方法得到。

另外生成函數(shù)也廣泛應(yīng)用于編程與算法設(shè)計(jì)、分析上，運(yùn)用這種數(shù)學(xué)方法往往對(duì)程序效率與速度有很大改進(jìn)。

普通型生成函數(shù)

定義：

對(duì)于任意數(shù)列 $a_0,a_1,a_2,\dots ,a_n$ 用下面這個(gè)函數(shù)來表示這個(gè)數(shù)列：$$G(x)=\sum _{i=0}^{\infty }{a}_i{x}^i=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+?+a_n{x}^n\dots$$這個(gè)函數(shù)就叫做數(shù)列的 生成函數(shù) ( $generatingfunction$ ) 。

指數(shù)型生成函數(shù)

定義：

對(duì)于任意數(shù)列 $h_0,h_1,h_2,\dots ,h_n$ 用下面這個(gè)函數(shù)來表示這個(gè)數(shù)列：$$G(x)=\sum _{i=0}^{\infty }{h}_i\frac{x^i}{i!}=h_0+h_1+h_{2}x+h_3\frac{x^2}{2!}+?+h_n\frac{x^n}{n!}+\dots$$

$\mathcal{T}ips:$在研究生成函數(shù)時(shí)，我們都假設(shè)級(jí)數(shù)收斂，因?yàn)樯珊瘮?shù)中的 $x$ 沒有實(shí)際意義。

例子

我們先來考慮這樣的一個(gè)問題：一個(gè)班上有四個(gè) $MM$ ，現(xiàn)在要從其中選出 $n$ 個(gè)做自己的老婆，請(qǐng)問有多少種選法？ 答案很簡(jiǎn)單， $\left(\genfrac{}{}{0ex}{}{4}{n}\right)$ 對(duì)吧。也就是說從 $i=0$ 開始， 問題的答案分別是 $1,4,6,4,1,0,0,0,\dots$ 那么它的生成函數(shù)應(yīng)該為 $G(x)=1+4x+6x^2+4x^3+x^4$ 。誒，這不就是二項(xiàng)式展開嗎？ 于是就有 $G(x)=(1+x{)}^4$ 。

這里有個(gè)廣義的推論： $(1+x{)}^k=(\genfrac{}{}{0ex}{}{k}{0})x^0+(\genfrac{}{}{0ex}{}{k}{1})x^1+?+(\genfrac{}{}{0ex}{}{k}{k})x^k+\dots$ ，其中，廣義的組合數(shù) $\left(\genfrac{}{}{0ex}{}{k}{i}\right)=\frac{k(k?1)(k?2)\dots (k?i+1)}{i!}$ 且 $k$ 為 實(shí)數(shù) 。
舉個(gè)例子： $\left(\genfrac{}{}{0ex}{}{4}{6}\right)=\frac{4\times 3\times 2\times 1\times 0\times (?1)}{6!}=0，\left(\genfrac{}{}{0ex}{}{?1.4}{2}\right)=\frac{(?1.4)\times (?2.4)}{2!}=1.68$
這個(gè)推論就是經(jīng)典的 牛頓二項(xiàng)式定理 。

接下來我們?cè)賮砜紤]一個(gè)更復(fù)雜的生成函數(shù)： 求出 $x_1+x_2+?+x_k=n$ 有多少個(gè)非負(fù)整數(shù)解。這道題在 $Chty\_syq$ 的課件中有詳細(xì)解答過。

把每組解的每個(gè)數(shù)加 $1$ ，就變成了 $x_1+x_2+?+x_k=n+k$ 的正整數(shù)解的個(gè)數(shù)了，這時(shí)候我們就可以用 隔板法 來做： 把 $n+k$ 個(gè)東西排成一排，在 $n+k?1$ 個(gè)間隔中插入 $k?1$ 個(gè) “隔板” ，所以答案就是 $\left(\genfrac{}{}{0ex}{}{n+k?1}{k?1}\right)=\left(\genfrac{}{}{0ex}{}{n+k?1}{n}\right)$ ，則它關(guān)于 $n$ 的生成函數(shù)是 $G(x)=(1?x{)}^{?k}$ 。

推導(dǎo)：
將 $(1?x{)}^{?k}$ 按照牛頓二項(xiàng)式展開后可以得到 $x^n$ 的系數(shù)恰好是 $\left(\genfrac{}{}{0ex}{}{n+k?1}{n}\right)$
因?yàn)檎归_后第n+1項(xiàng)： $\left(\genfrac{}{}{0ex}{}{?k}{n}\right)(?x{)}^n=[(?1{)}^n(\genfrac{}{}{0ex}{}{n+k?1}{n})][(?1{)}^n{x}^n]=(\genfrac{}{}{0ex}{}{n+k?1}{n})x^n$

經(jīng)典題目

1、求 Fibonacci 通項(xiàng)公式

---

在接下來的講解之前，我們還需要知道一個(gè)公式：$$\sum _{i=0}^{\infty }{x}^i=\frac{1}{1?x}$$這個(gè)公式在之前我已經(jīng)證明過了，再證一遍：$$\begin{array}{rl}& 已知等比數(shù)列求和公式：\sum _{i=0}^n{x}^i=\frac{1?x^{n+1}}{1?x}\\ & \because ?1<x<1\\ & \therefore \underset{n\to \infty }{\lim }{x}^{n+1}=0\\ & \therefore \sum _{i=0}^{\infty }{x}^i=\underset{n\to \infty }{\lim }\sum _{i=0}^n{x}^i=\underset{n\to \infty }{\lim }\frac{1?x^{n+1}}{1?x}=\frac{1}{1?x}\end{array}$$證畢。

---

已知 $Fibonacci$ 遞推數(shù)列為：$$\begin{array}{rl}& F(n)=F(n?1)+F(n?2)(n?3)\\ & F_2=F_1=1\end{array}$$設(shè)它的生成函數(shù)為 $g(x)$ ，則 $g(x)$ 為：$$\begin{array}{rl}g(x)& =x+x^2+2x^3+3x^4+\dots \\ & =F_1+F_2{x}^2+F_3{x}^3+\dots \end{array}$$兩邊同時(shí)乘以 $x$：$$x?g(x)=x^2+x^3+2x^4+3x^5+\dots$$用上式減下式可得：$$g(x)?x?g(x)=x+x^3+x^4+2x^5+3x^6+?=x+x^2?g(x)$$解得， $g(x)=\frac{x}{1?x?x^2}$ 。

由于這個(gè)式子不是之前我們見過的 $x$ 成等比關(guān)系的式子，再根據(jù)這是個(gè)分式，于是我們可以把它裂項(xiàng)成等比數(shù)列無窮級(jí)數(shù)求和的式子，將下半部分因式分解可得：$$g(x)=\frac{x}{(1?\frac{1?\sqrt{5}}{2}x)(1?\frac{1+\sqrt{5}}{2}x)}$$再轉(zhuǎn)變成和的形式：$$\begin{array}{rl}& 設(shè)g(x)=\frac{x}{(1?\frac{1?\sqrt{5}}{2}x)(1?\frac{1+\sqrt{5}}{2}x)}=\frac{a}{(1?\frac{1?\sqrt{5}}{2}x)}+\frac{b}{(1?\frac{1+\sqrt{5}}{2}x)}\\ & 通分一下得到，\\ & g(x)=\frac{(1?\frac{1+\sqrt{5}}{2}x)a+(1?\frac{1?\sqrt{5}}{2}x)b}{(1?\frac{1?\sqrt{5}}{2}x)(1?\frac{1+\sqrt{5}}{2}x)}\\ & \therefore (1?\frac{1+\sqrt{5}}{2}x)a+(1?\frac{1?\sqrt{5}}{2}x)b=x\\ & 又根據(jù)g(x)=0可以得到方程組：\\ & \{\begin{array}{ll}(1?\frac{1+\sqrt{5}}{2}x)a+(1?\frac{1?\sqrt{5}}{2}x)b=x& ???????①\\ a+b=0& ???????②\end{array}\\ & 將②帶回到①中可以得到，a=?\frac{1}{\sqrt{5}}\\ & \therefore b=\frac{1}{\sqrt{5}}\\ & ?g(x)=\frac{1}{\sqrt{5}}\frac{1}{(1?\frac{1+\sqrt{5}}{2}x)}?\frac{1}{\sqrt{5}}\frac{1}{(1?\frac{1?\sqrt{5}}{2}x)}\\ & 將其還原成數(shù)列展開得，\\ & g(x)=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2}x+(\frac{1+\sqrt{5}}{2}{)}^2{x}^2+?+(\frac{1+\sqrt{5}}{2}{)}^n{x}^n+\dots )?\frac{1}{\sqrt{5}}(\frac{1?\sqrt{5}}{2}x+(\frac{1?\sqrt{5}}{2}{)}^2{x}^2+?+(\frac{1?\sqrt{5}}{2}{)}^n{x}^n+\dots )\\ & g(x)=F_1+F_2{x}^2+F_3{x}^3+?+F_n{x}^n+\dots \\ & 于是我們可以得到Fibonacci的通項(xiàng)公式：\\ & F_n=\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n?\frac{1}{\sqrt{5}}{\left(\frac{1?\sqrt{5}}{2}\right)}^n\end{array}$$哎呦臥槽，這可把我碼的累死了！！！

總結(jié)

以上是生活随笔為你收集整理的生成函数学习笔记心得的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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