网站开发可行性技术方案,山东网站建设制作公司,代做关键词收录排名,网络市场营销的概念EGF中多项式exp的组合意义
EGF一般用来处理多重集的排列问题#xff0c;在其上可以定义多项式的exp运算#xff0c;在处理一类问题的时候有独特的作用
我们考虑将n个有标号的元素分为k个非空无序集合的方案数#xff0c;记其EGF为 F k F_{k} Fk,再考虑 f i f_i fi表示…EGF中多项式exp的组合意义
EGF一般用来处理多重集的排列问题在其上可以定义多项式的exp运算在处理一类问题的时候有独特的作用
我们考虑将n个有标号的元素分为k个非空无序集合的方案数记其EGF为 F k F_{k} Fk,再考虑 f i f_i fi表示在这个我们定义的集合中对集合元素的计数方式也就是考虑元素在集合内的排列方式的个数这是一个只跟集合大小有关的值那么根据生成函数的定义我们不难得到下式 F k ( n ) n ! k ! ∑ ∑ i 1 k a i n ∏ j 1 k f a j a j ! F_{k}(n)\frac{n!}{k!}\sum_{\sum_{i1}^{k}a_in}\prod_{j1}^{k}\frac{f_{a_j}}{a_j!} Fk(n)k!n!∑∑i1kain∏j1kaj!faj最后除以 k ! k! k!是因为这k个集合是无序的而原本的多个多项式卷积显然是有序的
现在我们记 F ( x ) ^ ∑ i 0 i n f f i x i i ! \hat{F(x)}\sum_{i0}^{inf}f_i\frac{x^i}{i!} F(x)^∑i0inffii!xi,也就是原本的 f i f_i fi的EGF
再记 G k ( x ) G_k(x) Gk(x)为 F k ( n ) F_k(n) Fk(n)的EGF则有 G k ( x ) ∑ n 0 i n f F k ( n ) x n n ! G_k(x)\sum_{n0}^{inf}F_k(n)\frac{x^n}{n!} Gk(x)∑n0infFk(n)n!xn ∑ n 0 i n f n ! k ! ( ∑ ∑ i 1 k a i n ∏ j 1 k f a j a j ! ) x n n ! \sum_{n0}^{inf}\frac{n!}{k!}(\sum_{\sum_{i1}^{k}a_in}\prod_{j1}^{k}\frac{f_{a_j}}{a_j!})\frac{x^n}{n!} ∑n0infk!n!(∑∑i1kain∏j1kaj!faj)n!xn 1 k ! ∑ n 0 i n f ( ∑ ∑ i 1 k a i n ∏ j 1 k f a j x a j a j ! ) \frac{1}{k!}\sum_{n0}^{inf}(\sum_{\sum_{i1}^{k}a_in}\prod_{j1}^{k}\frac{f_{a_j}x^{a_j}}{a_j!}) k!1∑n0inf(∑∑i1kain∏j1kaj!fajxaj) 1 k ! ( F ( x ) ^ ) k \frac{1}{k!}(\hat{F(x)})^k k!1(F(x)^)k
如果我们考虑所有 k ≥ 0 k\geq 0 k≥0,就有 ∑ k ≥ 0 G k ( x ) ∑ k ≥ 0 ( F ( x ) ^ ) k k ! e x p F ( x ) ^ \sum_{k\geq 0}G_k(x)\sum_{k\geq 0}\frac{(\hat{F(x)})^k}{k!}exp\hat{F(x)} ∑k≥0Gk(x)∑k≥0k!(F(x)^)kexpF(x)^
我们惊奇地发现 G ( x ) G(x) G(x)的指数生成函数居然就是 f x f_x fx的生成函数的exp
总结一下多项式exp的组合意义就是有标号元素构成的集合划分为任意个非空子集的总方案数。
来几个具体的例子 考虑大小为n的排列的个数是 n ! n! n!,其指数生成函数是 P ( x ) ∑ n ≥ 0 n ! x n n ! ∑ n ≥ 0 x n 1 1 − x P(x)\sum_{n\geq 0}\frac{n!x^n}{n!}\sum_{n\geq 0}x^n\frac{1}{1-x} P(x)∑n≥0n!n!xn∑n≥0xn1−x1
一个大小为n的圆排列个数是 ( n − 1 ) ! (n-1)! (n−1)!,其指数生成函数是 G ( x ) ∑ n ≥ 1 ( n − 1 ) ! x n n ! ∑ n ≥ 1 x n n − ln ( 1 − x ) l n ( 1 1 − x ) G(x)\sum_{n\geq 1}\frac{(n-1)!x^n}{n!}\sum_{n\geq 1}\frac{x^n}{n}-\ln(1-x)ln(\frac{1}{1-x}) G(x)∑n≥1n!(n−1)!xn∑n≥1nxn−ln(1−x)ln(1−x1)
不难发现 P ( x ) e x p G ( x ) P(x)expG(x) P(x)expG(x)
仔细理解一下众所周知一个大小为n的排列一定可以拆成若干个环每一个环内部的排列数就是一个圆排列的方案数所以大小为n的排列的方案数就是把 1 , 2... n 1,2...n 1,2...n分成若干个非空集合每一个集合的圆排列方案数之积这与我们上面讲到的exp的组合意义相符合 未完待续
