|
|
| |
|
| |
| |
| 一类排列问题的母函数解法 |
|
[ 2008-7-19 20:21:00 | By: wantnon ] |
生成函数概念：
则G称为所描述序列的生成函数，如果G的项给出所有符合描述的序列。
因此当说“某序列由某函数生成”是指此序列是这个函数的项。
下面例题及解法是参考这里
例：一个abc序列由a b c三种元素组成，a只能连续出现偶数个，b连续出现1个或3个，c任意，求这样的长度为n的序列的个数（a,b,c可以不全出现，(注1)）。
例子：aabaaaabbbcaaccccbbbaab
三个元素不易处理，先对b,c不加区别均用d代表，序列变为aadaaaaddddaadddddddaad.
即先解决“a连续出现偶数个，d未定”的ad序列的生成问题。
设a序列的生成函数为A.
设d序列的生成函数为D.
（均包含常数项1）
令
A'=A-1
B'=B-1
则有
aadddaaaad由A'D'A'D'生成，
dddaad由D'A'D'生成，
等等。
［注：用A',B'而不用A,B,以及A'与B'必须交错出现，都是为了保证序列加长过程中每段连续的若干个a(或者d)是一次性(而不能分两次)加上去的。“相同相邻的东西一次性搞定”是排列的基本原则，“相同的东西一次性搞定”是组合的基本原则，如果分多次搞，则会出现重复］
一般情况：(括号表循环节)
A'(D'A')：由$A'^2D'+A'^3D'^2+...={A'}/{1-A'D'}$生成。
D'(A'D')：由$D'^2A'+D'^3A'^2+...={D'}/{1-A'D'}$生成。
A'D'(A'D')：由$A'D'+A'^2D'^2+...={A'D'}/{1-A'D'}$生成。
D'A'(D'A')：由$D'A'+D'^2A'^2+...={D'A'}/{1-A'D'}$生成。
另外还要再算上1。
令$G={A'}/{1-A'D'}+{D'}/{1-A'D'}+{A'D'}/{1-A'D'}+{D'A'}/{1-A'D'}+1=1/{1/A+1/D-1}$...（1）
则G的项中就包含了所有的ad序列(包括1)，所以G就是ad序列的生成函数。
接下来是d的区分问题。
设b序列的生成函数为B.
c序列的生成函数为C.
(也均包括1).
考虑d序列(即bc序列)的生成，
同前可得$D=1/{1/B+1/C-1}$...(2)
将(2)代入(1)即可得
$G=1/{1/A+1/B+1/C-2}$
其中
A=$1+aax^2+aaaax^4+...=1+x^2+x^4+...$
B=$1+bx+b^3x^3=1+x+x^3$
C=$1+cx+c^2x^2+...=1+x+x^2+...$
(x指标长度)
总结：由本例可见，母函数可以进行组合及代换。
－－
注：1，如果条件改为"a,b,c必须全出现"，则需用容斥原理。
2，一般地若有m种字母$a_1,a_2,...,a_m$，则$G=1/{1/A_1+1/A_2+...+1/A_m-m+1}$.
3，对于有理母函数，其分母给出递推式。
4，此法适合于一类历史无关的排列问题求解。
|
|
| | |
|
