---
# System prepended metadata

title: discrete 9.1 生成函數

---

# discrete 9.1 生成函數
為了解決
$c_1+c_2+...+c_n=m$的有幾種方法的問題
## 先備知識
二項式定理$(1+x)^n=C^n_0+C^n_1x^1+C^n_2x^2+...+C^n_nx^n$
$1-x^{n+1}=(1-x)(1+x+x^2+...+x^n)$
so
$\frac{1-x^{n+1}}{(1-x)}=(1+x+x^2+...+x^n)$



# 9.2 生成函數
$(x+x^2+x^3+...)^n=x^n(1+x+x^2+...)^n=x^n(\frac{1}{(1-x)^n})$
又$(1+x)^{-n}=\sum\limits_{r = 0}^{\infty}{(-1x)^rC^{n+r-1}_r}$
$(x+x^2+x^3+...)^n=x^n(1+x+x^2+...)^n=x^n(\frac{1}{(1-x)^n})$
$=x^n\sum\limits_{r = 0}^{\infty}{(-1x)^rC^{n+r-1}_r}$
$=\sum\limits_{r = 0}^{\infty}{C^{n+r-1}_r}(-1)^rx^{n+r}$

![](https://i.imgur.com/yfjfwsY.png)


# ex
Determine the coefficient of $𝑥^{15}$ in $𝑓(𝑥)=(𝑥^2+𝑥^3+𝑥^4+…)^4$

$(𝑥^2+𝑥^3+𝑥^4+…)=𝑥^2$  
$(1+𝑥+𝑥^2+…)=𝑥^2/(1−𝑥)$  
$(𝑥^2+𝑥^3+𝑥^4+…)^4=𝑥^8(1−𝑥)^{−4}$  
$(𝑥^2+𝑥^3+𝑥^4+…)^4=𝑥^8\sum\limits_{r = 0}^{\infty}{(-1x)^rC^{4+r-1}_r}$  
n=4 r=7是根據$x^8還要補幾個x決定的這裡要補到15$
$\sum\limits_{r = 0}^{\infty}{C^{4+7-1}_7}(-1)^7x^{8+7}$


The coefficient of $𝑥^7$ in $(1−𝑥)^{−4}$is $C^{4+7-1}_7{(−1)}^7$ =120


# ex
Find the coefficient of 𝑥^12 in

$𝑓(𝑥)=(𝑥^4+𝑥^5+𝑥^6+𝑥^7+𝑥^8)(𝑥^2+𝑥^3+𝑥^4+𝑥^5+𝑥^6)(𝑥^2+𝑥^3+𝑥^4+𝑥^5)$
$\rightarrow x^8(1+𝑥+𝑥^2+𝑥^3+𝑥^4)(1+𝑥+𝑥^2+𝑥^3+𝑥^4 )(1+𝑥+𝑥^2+𝑥^3+𝑥^4 )$
![](https://i.imgur.com/bdgw9Z5.png)



# 9.3 partitions of integers

𝑝(𝑛): the number of partitioning a positive integer into positive summands without regard to order.

![](https://i.imgur.com/jEtv69G.png)


$P_d(n)=P_o(n)$
distinct
odd




