Skip to content

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

生成函数

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

(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(0e15),xe2(0e22),xe3(0e34)\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+)=11x2x1x21x51xx1x=x2(1x5)(1x2)2(1x)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(1x)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=0hnxnn!=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=0xnn!=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=0anxnn!=eax\displaystyle{ \sum _{ n = 0 } ^{ \infty } a ^{ n } \frac{ x ^{ n } }{ {n !} } = e ^{ a x } }
定理 7.3.1

hn\displaystyle{ h _{ n } } 是多重集合 {n1a1,,nkak}\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 }0m1n1,,0mknk\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 } 的组合 {m1a1,,mkak}\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+ex2)2e3x=14(e5x+2e3x+ex)=14(5nxnn!+23nxnn!+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 } }