Warning: session_start(): open(/tmp/sess_7afb4b1b1ac9b7c246ae034981f15451, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:生成函数_2 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:生成函数_2

指数生成函数(EGF)

算法简介

形如 $F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!}$ 的函数, $a_n$ 可以提供关于这个序列的信息,一般用于解决有标号组合计数问题。

基本运算

$$F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!},G(x)=\sum_{n=0}^{\infty}b_n\frac {x^n}{n!}$$

$$F(x)G(x)=\sum_{n=0}^{\infty}\sum_{i=0}^n a_ib_{n-i}\frac {x^n}{i!(n-i)!}=\sum_{n=0}^{\infty}\sum_{i=0}^n {n\choose i}a_ib_{n-i}\frac {x^n}{n!}$$

$$\sum_{n=0}^{\infty}k^n\frac {x^n}{n!}=e^{kx}$$

$$\sum_{n=0}^{\infty}n^{\underline k}\frac {x^n}{n!}=x^ke^x$$

算法例题

例题一

题意

定义贝尔数 $w_n$ 表示将集合 $\{1,2\cdots n\}$ 划分为若干个不相交非空集合的方案数,求 $w_n$。

题解

2020-2021/teams/legal_string/jxm2001/生成函数_2.1597235494.txt.gz · 最后更改: 2020/08/12 20:31 由 jxm2001