Skip to content
Notes

第七章 递推关系和生成函数

生成函数

什么样的数列，生成函数是如下式子

(1+x+x2+x3+x4+x5)(1+x+x2)(1+x+x2+x3+x4)\displaystyle{ \left( 1 + x + x ^{ 2 } + x ^{ 3 } + x ^{ 4 } + x ^{ 5 } \right) \left( 1 + x + x ^{ 2 } \right) \left( 1 + x + x ^{ 2 } + x ^{ 3 } + x ^{ 4 } \right) }
解
  • xe1(0⩽e1⩽5),xe2(0⩽e2⩽2),xe3(0⩽e3⩽4)\displaystyle{ x ^{ e _{ 1 } } \left( 0 \leqslant e _{ 1 } \leqslant 5 \right) , x ^{ e _{ 2 } } \left( 0 \leqslant e _{ 2 } \leqslant 2 \right) , x ^{ e _{ 3 } } \left( 0 \leqslant e _{ 3 } \leqslant 4 \right) } 分别是第一个、第二个、第三个因子
  • 假设 e1+e2+e3=n\displaystyle{ e _{ 1 } + e _{ 2 } + e _{ 3 } = n }，则 xe1xe2xe3=xn\displaystyle{ x ^{ e _{ 1 } } x ^{ e _{ 2 } } x ^{ e _{ 3 } } = x ^{ n } }
  • xn\displaystyle{ x ^{ n } } 的系数是 e1+e2+e3=n\displaystyle{ e _{ 1 } + e _{ 2 } + e _{ 3 } = n } 的整数解的个数 hn\displaystyle{ h _{ n } }，其中 e1,e2,e3\displaystyle{ e _{ 1 } , e _{ 2 } , e _{ 3 } } 满足上述的范围

确定 Apple, Banana, Orange, Pear 的 n\displaystyle{ n } 组合数，Apple 偶数，Banana 奇数，Orange ∈[0,4]\displaystyle{ \in \left[ 0 , 4 \right] }，Pear ⩾1\displaystyle{ \geqslant 1 }

解
  • 等价于接触 a+b+c+d=n\displaystyle{ a + b + c + d = n } 的非负整数解的个数 hn\displaystyle{ h _{ n } }，分别满足上述条件
  • 为每种水果创建一个因子，其中的指数为该类型水果的 n\displaystyle{ n } 组合中允许的数量
g(x)=(1+x2+x4+…)⋅(x+x3+x5+…)⋅(1+x+x2+x3+x4)⋅(x+x2+x3+…)=11−x2x1−x21−x51−xx1−x=x2(1−x5)(1−x2)2(1−x)2\displaystyle{ \begin{aligned}g \left( x \right) & = \left( 1 + x ^{ 2 } + x ^{ 4 } + \ldots \right) \\ & \cdot \left( x + x ^{ 3 } + x ^{ 5 } + \ldots \right) \\ & \cdot \left( 1 + x + x ^{ 2 } + x ^{ 3 } + x ^{ 4 } \right) \\ & \cdot \left( x + x ^{ 2 } + x ^{ 3 } + \ldots \right) \\ & = \frac{ 1 }{ 1 - x ^{ 2 } } \frac{ x }{ 1 - x ^{ 2 } } \frac{ 1 - x ^{ 5 } }{ 1 - x } \frac{ x }{ 1 - x } \\ & = \frac{ x ^{ 2 } \left( 1 - x ^{ 5 } \right) }{ \left( 1 - x ^{ 2 } \right) ^{ 2 } \left( 1 - x \right) ^{ 2 } }\end{aligned} }

类似的，Apple 偶数，Banana 5 的倍数，Orange 不超过 4 个，Pear 最多一个

g(x)=(1+x2+x4+…)(1+x5+x10+…)(1+x+x2+x3+x4)(1+x)=1(1−x)2=∑n=0∞(n+1n)xn=∑n=0∞(n+1)xn\displaystyle{ \begin{aligned}g \left( x \right) & = \left( 1 + x ^{ 2 } + x ^{ 4 } + \ldots \right) \left( 1 + x ^{ 5 } + x ^{ 10 } + \ldots \right) \left( 1 + x + x ^{ 2 } + x ^{ 3 } + x ^{ 4 } \right) \left( 1 + x \right) \\ & = \frac{ 1 }{ \left( 1 - x \right) ^{ 2 } } = \sum _{ n = 0 } ^{ \infty } { n + 1 \choose n } x ^{ n } \\ & = \sum _{ n = 0 } ^{ \infty } \left( n + 1 \right) x ^{ n }\end{aligned} }

指数生成函数

g(e)(x)=∑n=0∞hnxnn!=h0+h1x+h2x22!+h3x33!+hnxnn!+…\displaystyle{ \begin{aligned}g ^{ \left( e \right) } \left( x \right) & = \sum _{ n = 0 } ^{ \infty } h _{ n } \frac{ x ^{ n } }{ {n !} } \\ & = h _{ 0 } + h _{ 1 } x + h _{ 2 } \frac{ x ^{ 2 } }{ {2 !} } + h _{ 3 } \frac{ x ^{ 3 } }{ {3 !} } + h _{ n } \frac{ x ^{ n } }{ {n !} } + \ldots\end{aligned} }
  • 数列 {an=1}\displaystyle{ \left\lbrace a _{ n } = 1 \right\rbrace } 的指数生成函数为 g(e)(x)=∑n=0∞xnn!=ex\displaystyle{ g ^{ \left( e \right) } \left( x \right) = \sum _{ n = 0 } ^{ \infty } \frac{ x ^{ n } }{ {n !} } = e ^{ x } }
  • 数列 {1,a,a2,…}\displaystyle{ \left\lbrace 1 , a , a ^{ 2 } , \ldots \right\rbrace } 的指数生成函数为 ∑n=0∞anxnn!=eax\displaystyle{ \sum _{ n = 0 } ^{ \infty } a ^{ n } \frac{ x ^{ n } }{ {n !} } = e ^{ a x } }
定理 7.3.1

hn\displaystyle{ h _{ n } } 是多重集合 ≌{n1⋅a1,…,nk⋅ak}\displaystyle{ ≌ \left\lbrace n _{ 1 } \cdot a _{ 1 } , \ldots , n _{ k } \cdot a _{ k } \right\rbrace } 的 n\displaystyle{ n } 排列数，则数列 {hn}\displaystyle{ \left\lbrace h _{ n } \right\rbrace } 的指数生成函数

g(e)(x)=fn1(x)fn2(x)…fnk(x)\displaystyle{ g ^{ \left( e \right) } \left( x \right) = f _{ n _{ 1 } } \left( x \right) f _{ n _{ 2 } } \left( x \right) \ldots f _{ n _{ k } } \left( x \right) }

其中 fni(x)=1+x+x22!+…+xnini!\displaystyle{ f _{ n _{ i } } \left( x \right) = 1 + x + \frac{ x ^{ 2 } }{ {2 !} } + \ldots + \frac{ x ^{ n _{ i } } }{ {n _{ i } !} } }

展开 g(e)(x)\displaystyle{ g ^{ \left( e \right) } \left( x \right) } 得到项

xm1m1!xm2m2!…xmkmk!=xm1+…+mkm1!m2!…mk!=n!m1!m2!…mk!xnn!\displaystyle{ \frac{ x ^{ m _{ 1 } } }{ {m _{ 1 } !} } \frac{ x ^{ m _{ 2 } } }{ {m _{ 2 } !} } \ldots \frac{ x ^{ m _{ k } } }{ {m _{ k } !} } = \frac{ x ^{ m _{ 1 } + \ldots + m _{ k } } }{ {m _{ 1 } !} {m _{ 2 } !} \ldots {m _{ k } !} } = \frac{ {n !} }{ {m _{ 1 } !} {m _{ 2 } !} \ldots {m _{ k } !} } \frac{ x ^{ n } }{ {n !} } }

其中 n=Σm\displaystyle{ n = \Sigma m }，0⩽m1⩽n1,…,0⩽mk⩽nk\displaystyle{ 0 \leqslant m _{ 1 } \leqslant n _{ 1 } , \ldots , 0 \leqslant m _{ k } \leqslant n _{ k } }

xnn!\displaystyle{ \frac{ x ^{ n } }{ {n !} } } 的系数是 ∑n!m1!m2!…mk!\displaystyle{ \sum \frac{ {n !} }{ {m _{ 1 } !} {m _{ 2 } !} \ldots {m _{ k } !} } }

S\displaystyle{ S } 的组合 {m1⋅a1,…,mk⋅ak}\displaystyle{ \left\lbrace m _{ 1 } \cdot a _{ 1 } , \ldots , m _{ k } \cdot a _{ k } \right\rbrace } 的排列数为 n!m1!m2!…mk!\displaystyle{ \frac{ {n !} }{ {m _{ 1 } !} {m _{ 2 } !} \ldots {m _{ k } !} } }

例：hn\displaystyle{ h _{ n } } 表示由数字 1, 2, 3 构造的 n\displaystyle{ n } 位数的个数，1 有偶数个，2 至少有三个，3 最多四个，确定指数生成函数

解
h1(x)=1+x22!+x44!+…h2(x)=x33!+x44!+x55!…h3(x)=1+x+x22!+x33!+x44!\displaystyle{ \begin{aligned}h _{ 1 } \left( x \right) & = 1 + \frac{ x ^{ 2 } }{ {2 !} } + \frac{ x ^{ 4 } }{ {4 !} } + \ldots \\ h _{ 2 } \left( x \right) & = \frac{ x ^{ 3 } }{ {3 !} } + \frac{ x ^{ 4 } }{ {4 !} } + \frac{ x ^{ 5 } }{ {5 !} } \ldots \\ h _{ 3 } \left( x \right) & = 1 + x + \frac{ x ^{ 2 } }{ {2 !} } + \frac{ x ^{ 3 } }{ {3 !} } + \frac{ x ^{ 4 } }{ {4 !} }\end{aligned} }g(e)(x)=h1(x)h2(x)h3(x)\displaystyle{ g ^{ \left( e \right) } \left( x \right) = h _{ 1 } \left( x \right) h _{ 2 } \left( x \right) h _{ 3 } \left( x \right) }

例：确定满足条件的 n\displaystyle{ n } 位数的个数 hn\displaystyle{ h _{ n } }：每个数字都是奇数，且数字 1 和 3 出现次数为偶数

解

hn\displaystyle{ h _{ n } } 等于多重集合 {∞⋅1,∞⋅3,∞⋅5,∞⋅7,∞⋅9}\displaystyle{ \left\lbrace \infty \cdot 1 , \infty \cdot 3 , \infty \cdot 5 , \infty \cdot 7 , \infty \cdot 9 \right\rbrace } 的 n\displaystyle{ n } 排列中 1, 3 出现偶数次的 n\displaystyle{ n } 排列数

g(e)(x)=(1+x22!+x44!+…)2(1+x+x22!+…)3=(ex+e−x2)2e3x=14(e5x+2e3x+ex)=14(∑5nxnn!+2∑3nxnn!+∑xnn!)=∑n=0∞(5n+2×3n+14)xnn!\displaystyle{ \begin{aligned}g ^{ \left( e \right) } \left( x \right) & = \left( 1 + \frac{ x ^{ 2 } }{ {2 !} } + \frac{ x ^{ 4 } }{ {4 !} } + \ldots \right) ^{ 2 } \left( 1 + x + \frac{ x ^{ 2 } }{ {2 !} } + \ldots \right) ^{ 3 } \\ & = \left( \frac{ e ^{ x } + e ^{ {-x } } }{ 2 } \right) ^{ 2 } e ^{ 3 x } \\ & = \frac{ 1 }{ 4 } \left( e ^{ 5 x } + 2 e ^{ 3 x } + e ^{ x } \right) \\ & = \frac{ 1 }{ 4 } \left( \sum 5 ^{ n } \frac{ x ^{ n } }{ {n !} } + 2 \sum 3 ^{ n } \frac{ x ^{ n } }{ {n !} } + \sum \frac{ x ^{ n } }{ {n !} } \right) \\ & = \sum _{ n = 0 } ^{ \infty } \left( \frac{ 5 ^{ n } + 2 \times 3 ^{ n } + 1 }{ 4 } \right) \frac{ x ^{ n } }{ {n !} }\end{aligned} }

hn=5n+2×3n+14\displaystyle{ h _{ n } = \frac{ 5 ^{ n } + 2 \times 3 ^{ n } + 1 }{ 4 } }