剑锋所指,心之所向。

  1. 求和
  2. 差分
  3. 有限积分(前缀和)
  4. 二项式反演

求和

对于递推式:

T_0 = \alpha \\ a_nT_n = b_nT_{n - 1} + c_n \tag{1.1}

求出第 n 项的通项公式。


引入求和因子 s_n,满足:

s_{n - 1}a_{n - 1} = s_nb_n \tag{1.2}

S_n =\begin{cases} T_0 & n = 0 \\ s_na_nT_n & n > 0 \end{cases} \tag{1.3}

则重写递归式我们可以得到:

\begin{aligned} S_n &= s_na_nT_n\\ &= s_nb_nT_{n - 1}+s_nc_n \\ &=s_{n - 1}a_{n-1}T_{n - 1} + s_nc_n \\ &=S_{n - 1} + s_nc_n \end{aligned} \tag{1.4}

故我们得到了:

S_n = S_{n - 1} + s_nc_n \tag{1.5}

发现这是一个前缀和的形式,改写成和式为:

S_n = T_0 + \sum_{i = 1}^n s_ic_i \tag{1.6}

又由于:

s_n = \dfrac{a_{n - 1}}{b_n} \times s_{n - 1} \tag{1.7}

这是一个前缀积的形式,改写成积式为:

s_n = s_0 \times \prod_{i = 1}^{n} \dfrac{a_{i - 1}}{b_i} \tag{1.8}

由于 s_0 没有定义,但不难发现应该为单位元 1,所以:

s_n = \prod_{i = 1}^n \dfrac{a_{i - 1}}{b_i} \tag{1.9}

那么有:

\begin{aligned} \color{red} T_n &= \dfrac{S_n}{s_na_n} \\ & \color{red} = (a_n \times \prod_{i = 1}^n \dfrac{a_{i - 1}}{b_i})^{-1} * (T_0 + \sum_{i = 1}^n s_ic_i) \end{aligned} \tag{1.10}

差分

定义

对于函数 f(x),定义映射 E^a : f(x) \mapsto f(x + a),特别的,记 E^1E,记 E^0I

\Delta f(x) = E - I \tag{2.1.1}

\Delta : f(x) \mapsto f(x + 1) - f(x) \tag{2.1.2}

定义 k 阶差分:

\begin{aligned} \color{red} \Delta^k f(x) &= \Delta(\Delta^{k - 1} f(x)) \\ &= (E - I)^k f(x) \\ &= \sum_{i = 0}^k \binom{k}{i}E^k(-I)^{k - i}f(x) \\ &\color{red}= \sum_{i = 0}^k \binom{k}{i}(-1)^{k - i}f(x + k) \end{aligned} \tag{2.1.3}

性质

差分为线性符号。

\begin{aligned} \color{red} \Delta(c\times f(x)) &= c\times f(x + 1) - c \times f(x) \\ &\color{red}= c\times \Delta(f(x)) \end{aligned} \tag{2.2.1} \begin{aligned} \color{red} \Delta(u(x) + v(x)) &= u(x + 1) + v(x + 1) - u(x) + v(x) \\ &\color{red}= \Delta(u(x)) - \Delta(v(x)) \end{aligned} \tag{2.2.2} \begin{aligned} \color{red} \Delta(u(x) \times v(x)) &= u(x + 1) \times v(x + 1) - u(x) \times v(x) \\ &= u(x + 1) \times v(x + 1) - u(x) \times v(x) + u(x) \times v(x + 1) - u(x) \times v(x + 1) \\ &= v(x + 1) \times [u(x + 1) - u(x)] - u(x) \times [v(x + 1) - v(x)] \\ &\color{red}= E(v(x)) \times \Delta(u(x)) - u(x) \times \Delta(v(x)) \end{aligned} \tag{2.2.3}

结论

\color{red}\Delta(x^{\underline{n}}) = n \times x^{\underline{n - 1}} \tag{2.3.1}

可以发现上述性质与 (x^n)' = n \times x^{n - 1} 十分类似。

\color{red}\Delta(a^x) = (a - 1) \times a^x \tag{2.3.2}

可以发现上述性质与 (a^x)' = \ln a \times a ^x 有些类似。

有限积分

定义

有限积分符号:

\sum_{k = a}^b f(k) \tag{3.1.1}

表示对于所有 k \in [a, b]f(k) 的和。

对于函数 f(x) 的离散反导函数,可以简写为 \sum f(x)

性质

类似积分基本定理,我们有:

\color{red}\sum_{k = a}^b f(k) = g(b + 1) - g(a) \tag{3.2.1}

其中,g(x)f(x) 的离散反导函数,满足 \Delta(g(x)) = f(x)

有限积分符号为线性符号。

\color{red}\sum [c \times f(x)] = c \times \sum f(x) \tag{3.2.2}

乘法分配律。

\color{red}\sum [u(x) + v(x)] = \sum u(x) + \sum v(x) \tag{3.2.3} \color{red} \sum[u(x) \times \Delta(v(x))] = u(x) \times v(x) - \sum \Delta(u(x))E(v(x)) \tag{3.2.4}

上式可以从 (2.2.3) 变形而得。

结论

\color{red} \sum x^{\underline{n}} = \begin{cases} \dfrac{x^{\underline{n + 1}}}{n + 1} & n \neq -1 \\ H_x & n = -1 \end{cases} \tag{3.3.1} \color{red} \sum a^x = \begin{cases} \dfrac{a^x}{a - 1} & a \neq 1 \\ x & a = 1 \end{cases} \tag{3.3.2} \color{red}\sum x^n = \sum_{k = 0}^nS_{n, k} \times \dfrac{(n + 1)^{\underline{k +1}}}{k + 1} \tag{3.3.3}

二项式反演

反演原理

对于和式:

\begin{aligned} &g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k}\\ &f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k} \end{aligned}

如果对于所有合法的 m,都有:

\sum_{k = m}^n a_{n, k} \times b_{k, m} = [n = m]

那么:

\color{red}g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Longleftrightarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}

\text{proof}:

g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} 带入 f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}

g_{n}=\sum_{k=0}^{n} a_{n, k} \sum_{m=0}^{k} b_{k, m} g_{m}=\sum_{m=0}^{n} g_{m} \sum_{k=m}^{n} a_{n, k} b_{k, m}

如果有:\sum_{k=m}^{n} a_{n, k} b_{k, m}=[n=m] 则 :

g_{n}=\sum_{m=0}^{n} g_{m}[n=m]=g_{n}

所以有:

g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Leftarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}

用类似的方法可以得到:

g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Rightarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}

综上有:

g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Longleftrightarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}

二项式反演

离散麦克劳伦公式:

对于 n 次多项式 f(x),有:

f(x) = \sum_{k = 0}^n \binom{x}{k} \Delta^kf(0)

而对于 (2.1.3),我们有:

\Delta^k(f(0)) = \sum_{i = 0}^k \binom{k}{i}(-1)^{k - i}f(k)

u_n = \Delta^nf(0), v_n = f(n),那么有:

u_n = \sum_{i = 0}^k \binom{k}{i}(-1)^{k - i}v_k \\ v_n = \sum_{k = 0}^n \binom{n}{k} u_k

则我们希望得到:

u_n = \sum_{k = 0}^n \binom{n}{k}(-1)^kv_k \Longleftrightarrow v_n = \sum_{k = 0}^n \binom{n}{k} u_k

\text{proof}:

u_k \leftarrow (-1)^k u_k 根据反演原理,只要:

\begin{aligned} [n = m ] &= \sum_{k = m}^n \binom{n}{k}(-1)^k \binom{k}{m}(-1)^m \\ &= (-1)^m\sum_{k = m}^n (-1)^k \times \dfrac{n!}{k! \times (n - k)!} \times \dfrac{k!}{m! \times (k - m)!} \times \dfrac{(n - m)!}{(n - m)!} \\ &= (-1)^m \sum_{k = m}^n (-1)^k \times \dfrac{n!}{m! \times (n -m)!} \times \dfrac{(n - m!)}{(n - k)! \times (k - m)!} \\ &= (-1)^m \sum_{k = m}^n (-1)^k \binom{n}{m} \binom{n - m}{n - k} \\ &= (-1)^m \binom{n}{m} \sum_{k = m}^n (-1)^k \binom{n - m}{n - k} \\ &= (-1)^m \binom{n}{m} \sum_{k = 0}^{n - m} (-1)^{n - k} \binom{n - m}{n - m - k} \\ &= (-1)^m \binom{n}{m} \sum_{k = 0}^{n - m} (-1)^{n - k} \binom{n - m}{k} \\ &= (-1)^{m + n} \binom{n}{m} \sum_{k = 0}^{n - m} (-1)^k \binom{n - m}{k}1^{n - m - k}\\ &= (-1)^{m + n} \binom{n}{m} (1 - 1)^{n - m} \\ &= (-1)^{m + n} \binom{n}{m} 0^{n - m} \end{aligned}

m \neq n 时,上式显然为 0。而 n = m 时,等于 1。故满足反演原理。

故:

\color{red} u_n = \sum_{k = 0}^n \binom{n}{k}(-1)^kv_k \Longleftrightarrow v_n = \sum_{k = 0}^n \binom{n}{k} u_k

OI-数学-离散数学 OI-数学-差分 OI-数学-有限积分 OI-数学-反演-二项式反演

斜率优化学习笔记
上一篇 «
CWOI 3-28 测试题解与总结
» 下一篇