前置芝士
普通型生成函数
是什么？
对于一个无穷项的序列 (a_0, a_1, a_2, a_3,...)，定义它的普通生成函数为
[f(x) = sum_{i = 0} ^ infty a_i x^i
]
这里 (x^i) 仅仅是用作记号
比如我有好多种物品((a, b, c))，每种物品分别有 (k_i) 种重量，每种物品只能选一个，求重量是 (t) 的方案数
我们让
[(x^{a_{x_1}} + x^{a_{x_x}}+...) * (x^{b_{x_1}} + x^{b_{x_2}} + ...) * (x^{c_{x_1}}+...)
]
最终答案就是 (x^t) 的系数
指数生成函数
定义：
对于一个无穷项序列 (a_0, a_1, a_2, a_3,...)，定义它的指数生成函数为级数：
[sum_{k = 0} ^ infty a_k frac {x ^ k} {k!}
]
普通生成函数一般用来解决无标号计数问题，指数生成函数常用来解决带标号计数问题。
一般我们给一个排列戴个帽子表示指数生成函数 (p(n) o widehat{p}(x)) 大小写随意
泰勒级数
就是一些特定式子泰勒展开后类似生成函数的形式
常见的泰勒级数
[egin{aligned}
e^x &= sum_{n = 0} ^ infty frac {x ^ n} {n!} \
ln(x + 1) &= sum_{n = 1} ^ infty frac {(-1)^{n + 1}} n x^n \
frac 1 {1 - x} &= sum_{n = 0} ^ infty x^n \
sin(x) &= sum_{n = 0} ^ infty frac {(-1) ^ n} {(2n + 1)!} x^{2n + 1} \
cos(x) &= sum_{n = 0} ^ infty frac{(-1)^n} {(2n)!} x^{2n} \
(1 + x)^a &= sum_{n = 0} ^ infty frac{a^{underline{n}}} {n!} x^n
end{aligned}]
小问号，你是否有很多朋友？看看麦克劳林展开就没了，咳咳
一些结论
part1
- 当 (p_n) 可以表示成一些 (c_k) 的不交并，(widehat{p}(x) = e^{widehat{c}(x)})
举个例子，排列 (p(n) = n!)，环排列 (c(n) = (n - 1)!)
我们在小学二年级的时候学过，排列可以看成置换，置换由一些轮换组成，也就是说，排列由一些环排列组成
[egin{aligned}
widehat{p}(x) &= sum_{n = 0} ^ infty p(n) frac{x^n} {n!} = frac 1 {1 - x} \
widehat{c}(x) &= sum_{n = 0} ^ infty c(n) frac{x ^ n} {n!} = -ln(1 - x) = ln(frac{1} {1 - x}) \
widehat{p}(x) &= e^{widehat{c}(x)}
end{aligned}]
但是我们想要证明这个结论，不能用到 (p) 和 (c) 的性质
设 (q_k(n)) 表示由 (k) 个轮换组成的大小为 (n) 的置换的方案数
枚举排列由几个环排列组成
[egin{aligned}
p(n) &= sum_{k = 0} ^ n q_k(n) \
widehat{p}(x) &= sum_{n = 0} ^ infty sum_{k = 0} ^ n q_k(n) frac{x^n} {n!} \
&= sum_{k = 0} ^ infty sum_{n = 0} ^ infty frac{q_k(n) x^n} {n!}
end{aligned}]
考虑怎么求 (q_k(n))，首先 (q_1(n) = c(n),widehat{q_1}(x) = widehat{c}(x))
在求 (q_2) 的时候考虑枚举一个环的大小，把 (c(0)) 看做 (0)
[q_2(n) = frac 1 2 sum_{k = 0} ^ n inom n k c(k) c(n - k)
]
因为 (inom n k) 是随便选一个环，我想要的是含有编号 (1) 的第一个环，枚举会重复所以 (/2)，那么
[egin{aligned}
widehat{q_2}(x) &= frac 1 2 sum_{n = 0} ^ infty frac{x ^ n} {n!} sum_{k = 0} ^ n inom n k c(k) c(n - k) \
&= frac 1 2 sum_{n = 0} ^ infty sum_{k = 0} ^ n frac{c(k) x^k} {k!} frac{c(n - k) x^{n - k}} {(n - k)!} \
&= frac 1 2 widehat{c}(x) ^ 2
end{aligned}]
继续推 (q_3(n)) 发现
[widehat{q_3}(x) = frac 1 {3!} widehat{c}(x)^3
]
于是我们知道了
[widehat{q_k}(x) = frac 1 {k!} widehat{c}(x) ^ k
]
那么,设 (widehat{q_0}(x) = frac 1 {0!}widehat{c}(x)^0)
[widehat{p}(x) = sum_{k = 0} ^ infty widehat{q_k}(x) = sum_{k = 0} ^ infty frac {widehat{c}(x)^k} {k!} = e^{widehat{c}(x)}
]
证毕
错排数的生成函数
考虑错排也是排列，只不过轮换的大小 (>1)
回到之前的式子，让(c(1) = 0)，就完美满足了轮换 (>1) 的要求
那 (widehat{c}(x)) 没有了 (frac {c(1)} {1!} x^1) 新的 (widehat{c}'(x) = widehat{c}(x) - x)
[widehat{P}(x) = e^{widehat{c}(x) - x} = e^{ln(frac 1 {1 + x}) - x} = frac {e^{-x}} {1 - x}
]
无向联通图的生成函数
我们要求出无向联通图的生成函数 (widehat{B}(x))
考虑无向图个数 (a(n) = 2^{inom n 2})
无向图是无向联通图的不交并
[widehat{A}(x) = e^{widehat{B}(x)}
]
[widehat{B}(x) = ln(widehat{A}(x))
]
多项式操作