母函數(shù)—解決計(jì)數(shù)

普母函數(shù)—組合問(wèn)題
指母函數(shù)—排列問(wèn)題

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?x+C_n^2?x^2+...+C_n^n?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!?n!}=\frac{2^n?n!}{n!?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}$

數(shù)的拆分

把正整數(shù) 拆分成 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}$

遞推關(guān)系

$$\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$

常系數(shù)線性齊次遞推關(guān)系

1.遞推關(guān)系—
2.特征方程 線性齊次方程
3.求解-----特征根 q
由$a_n=q^n$是方程的解 寫(xiě)出通解的形式，
將初值帶入即可得到遞推關(guā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}$
求遞推關(guān)系

$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$ 有幾個(gè)根有幾項(xiàng)

q 最終為1，忽略掉了

$x^2?2x+1=0$
特征根相同時(shí)，$$\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}$$多項(xiàng)式除法
$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?c_4=0\\ a_2=c_1+c_2?2+4c_3+c_4?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$

常系數(shù)線性非齊次遞推關(guān)系

1.找出遞推關(guān)系
2.找出齊次遞推關(guān)系，求出齊次的通解，然后求特解，從而得到遞推關(guān)系

漢諾塔遞推關(guān)系

求解齊次方程$a_n?2a_{n?1}=0$
特征方程 q =2
$a_n^{?}=c?2^n$
由于f(n)=1 (上面丟掉的)

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