$$
p_0, p_1, \cdots
$$
Consider the following generating function
$$
f(t)=\sum_{n=0}^\infty p_n t^n
$$

考虑中间有一项

$$p_nt^n$$

摇色子，摇一次

$$
\left(\frac16t+\frac16t^2+\frac16t^3+\frac16t^4+\frac16t^5+\frac16t^6\right)
$$

$$
p_nt^n\left(\frac16t+\frac16t^2+\frac16t^3+\frac16t^4+\frac16t^5+\frac16t^6\right)
$$

$$
=\left(\frac{p_n}6t^{n+1}+\frac{p_n}6t^{n+2}+\frac{p_n}6t^{n+3}+\frac{p_n}6t^{n+4}+\frac{p_n}6t^5+\frac{p_n}6t^6\right)
$$

摇两次，实际上是乘两次 是乘以
$$
\left(\frac16t+\frac16t^2+\frac16t^3+\frac16t^4+\frac16t^5+\frac16t^6\right)^2
$$

$f(t)$的第n个系数 是 玩家在整个游戏中去过第n个格子的概率

$\left(\frac16t+\frac16t^2+\frac16t^3+\frac16t^4+\frac16t^5+\frac16t^6\right)^2f(t)$ 是

玩家在整个游戏中在至少走过一步之后到达第n个格子的概率

因此必须有

$$
f(t) -1= \left(\frac16t+\frac16t^2+\frac16t^3+\frac16t^4+\frac16t^5+\frac16t^6\right)^2 f(t)
$$

其中 $P(t)$ 是个多项式

移项
$$
f(t) \left(1-\left(\frac16t+\frac16t^2+\frac16t^3+\frac16t^4+\frac16t^5+\frac16t^6\right)^2\right)= 1
$$

$$
f(t)=\frac{1}{1-\left(\frac16t+\frac16t^2+\frac16t^3+\frac16t^4+\frac16t^5+\frac16t^6\right)^2 }
$$

$$
f(t) = \frac{36}{36-(t+t^2+t^3+t^4+t^5+t^6)^2}
$$

因此，只需要知道$C_1$ for $$
f(t)=
f(t)=\frac{C_1}{t-1}+\frac{C_2}{t-x_2}+\cdots+\frac{C_n}{t-x_n}
$$

$$
(t-1)f(t)=C_1+(t-1)乱七八糟
$$

只需要求

$$
\left.\frac{36(t-1)}{36-(t+t^2+t^3+t^4+t^5+t^6)^2}\right|_{t=1}
$$

用洛必达法则，分子分母同时求导再代入1

$$
\left.\frac{36}{-2(1+2t+3t^2+4t^3+5t^4+6t^5)(t+t^2+t^3+t^4+t^5+t^6)}\right|_{t=1}=-\frac17
$$

回头看

$$
\frac{\frac17}{1-t}=\frac17+\frac17t+\frac17t^2+\cdots
$$

### 分式分解
**Statement**如果$P,Q$是两个多项式，且
$$
f(t)=\frac{P(x)}{Q(x)}
$$

如果$\deg Q>\deg P$ 而且$Q$没有重根

则我们一定可以把该函数写成
$$
f(t)=\frac{C_1}{t-x_1}+\frac{C_2}{t-x_2}+\cdots+\frac{C_n}{t-x_n}
$$

为什么有用？

$$
\frac1{t-1}=-(1+t+t^2+t^3+\cdots)
$$

$$
\frac1{t-2}=-\frac12-\frac14t-\frac18x^2-\cdots
$$

</br></br></br></br></br></br></br>