[组合数学]母函数与递推关系

母函数—解决计数

普母函数—组合问题
指母函数—排列问题

f(x)=$$\begin{gathered} {\sum }_{i=1}^n{a}_i{x}^i= \\ {a}_0+a_{1}x+a_2{x}^2+a_3{x}^3+...+a_n{x}^n \\ {C}_n^0+C_n^1\ast x+C_n^2\ast x^2+...+C_n^n\ast x^n= \end{gathered}$$ $(1+x{)}^n$
$(1+x{)}^n={\sum }_{k=0}^n{C}_n^k{x}^k={\sum }_{k=0}^n{C}_n^{n-k}{x}^k$

${\sum }_{k=0}^{\infty }(-1{)}^k{C}_{n+k-1}^k{z}^k=\frac{1}{(1+z{)}^n}=(1+z{)}^{-n}$

$(1+z{)}^{\alpha }={\sum }_{k=0}^{\infty }{C}_{\alpha }^k{z}^k$

$(1-z{)}^{-n}=\frac{1}{(1-z{)}^{-n}}={\sum }_{k=0}^{\infty }{C}_{n+k-1}^k{z}^k其中|z|<1$

${\sum }_{n=1}^{\infty }{C}_{2n}^n{x}^n=(1-4x{)}^{-\frac{1}{2}}$

$其中C_{2n}^n=\frac{2n!}{n!\ast n!}=\frac{2^n\ast n!}{n!\ast n!}=\frac{2^n}{n!}$

$\frac{1}{(1+x)}={\sum }_{k=0}^{\infty }{C}_{-1}^k{z}^k={\sum }_{k=0}^{\infty }(-1{)}^k{x}^k$

$\frac{1}{1-x}={\sum }_{n=0}^{\infty }{x}^n$

$\frac{1}{(1-x{)}^2}={\sum }_{n=0}^{\infty }(n+1)x^n$

$\frac{2}{(1-x{)}^3}={\sum }_{n=2}^{\infty }n(n-1)x^{n-2}$

$\frac{6}{(1-x{)}^4}={\sum }_{n=3}^{\infty }n(n-1)(n-2)x^{n-3}$

$f(x)=a_0+a_1\frac{x_1}{1!}+a_2\frac{x^2}{2!}+...+a_n\frac{x^n}{n!}$

$e^{ax}=1+a\frac{x}{1!}+a^2\frac{x^2}{2!}+...+a^n\frac{x^n}{n!}+...$

$e^{-x}=1-\frac{x}{1!}+\frac{x^2}{2!}+...+(-1{)}^n\frac{x^n}{n!}...$

$e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x^n}{n!}...$

$sin(x)=\frac{x}{1}+\frac{x^3}{3!}+\frac{x^{2n-1}}{(2n-1)!}+...=\frac{e^x-e^{-x}}{2}$
$cos(x)=1+\frac{x^2}{2!}+\frac{x^4}{4!}+...+\frac{x^{2n}}{2n!}+...=\frac{e^{-x}+e^x}{2}$

2m 1n 1r

组合 球相同 盒子不同 不能是空 $C_{n-1}^{m-1}$

数的拆分

把正整数 拆分成 a b c 的和的方法P(n)
$\frac{1}{(1-x^a)(1-x^b)(1-x^c)}=(1+x^a+x^{2a}+...)(1+x^b+x^{2b}+...)(1+x^c+x^{2c}+...)$

$(1+x)(1+x^2)(1+x^3)(1+x^4)$

$1-x^2=\frac{1+x}{1-x}$
$1+x^2=\frac{1-x^4}{1-x^2}$
$\frac{1-x^{2n}}{1-x}=1+x+x^2+...+x^{2n-1}$

递推关系

$$\begin{gathered} F_n-F_{n-1}-F_{n-2}=0 \\ {F}_{n-1}-F_{n-2}-F_{n-3}=0 \end{gathered}$$


$C(x)=x^n-b_1{x}^{n-1}-b_2{x}^{n-2}...=0$

常系数线性齐次递推关系

1.递推关系—
2.特征方程 线性齐次方程
3.求解-----特征根 q
由$a_n=q^n$是方程的解 写出通解的形式，
将初值带入即可得到递推关系

$\{\begin{array}{l}{a}_n=2a_{n-1}+a_n-2-2a_{n-3}(n\ge 3)\\ a_0=1,a_1=2;a_2=0\end{array}$
求递推关系

$x^3-2x^2-x+2=0$
(x+1)(x-1)(x-2)=0
特征根是 -1 1 2
$q_1=1q_2=-1q_3=2$

通解形式为 $a_n=c_1{q}^n+c_2{q}^n+c_3{q}^n$ 有几个根有几项

q 最终为1，忽略掉了

$x^2-2x+1=0$
特征根相同时，$$\begin{gathered} q_1=q_2=1 \\ {a}_n=c_1+c_{2}n \end{gathered}$$

$\{\begin{array}{l}{a}_n=-a_{n-1}+3a_n-2+5a_{n-3}+2a_{n-4}(n\ge 4)\\ a_0=1,a_1=0,a_2=1,a_3=2\end{array}$

$$\begin{gathered} x^4+x^3-3x^2-5x-2=0 \\ q1=q2=q3=-1,q4=2 \end{gathered}$$多项式除法
$a_n=c_1(-1{)}^n+c_{2}n(-1{)}^n+c_3{n}^2(-1{)}^n+c_4{2}^n$

$\{\begin{array}{l}{a}_0=c_1+c_4=1\\ a_1=-c_1-c_2-c_3+2\ast c_4=0\\ a_2=c_1+c_2\ast 2+4c_3+c_4\ast 4=1\\ a_3=-c_1-3c_2-9c_3+8_{c}4=2\end{array}$

$c_1=\frac{42}{52},c_2=-\frac{29}{52},c_3=\frac{7}{52},c_4=\frac{10}{52}$
$a_n=\frac{42}{52}(-1{)}^n-\frac{29}{52}n(-1{)}^n+\frac{7}{52}{n}^2(-1{)}^n+\frac{10}{52}{2}^n$

$$\begin{gathered} x^3+6x^2+12x+8=0 \\ (x+2{)}^3=0 \end{gathered}$$
$(c_1+c_{2}n+c_3{n}^2=a_n$

常系数线性非齐次递推关系

1.找出递推关系
2.找出齐次递推关系，求出齐次的通解，然后求特解，从而得到递推关系

汉诺塔递推关系

求解齐次方程$a_n-2a_{n-1}=0$
特征方程 q =2
$a_n^{\ast }=c\ast 2^n$
由于f(n)=1 (上面丢掉的)

m=1 n=1 k=0 an=A
a2=3 = c1*2^n+A
A=-1