杨表学习笔记

本文大量参考袁方舟的论文《浅谈杨氏矩阵在信息学竞赛中的应用》。

Part 1 定义

定义 1.1（拆分）

定义正整数 $n$ 的拆分 $\lambda_{[1,k]}=\{\lambda_{1},\lambda_{2},\dots,\lambda_{k}\}$，其需要满足：

• $\forall 1\le i\le k$，都有 $\lambda_i\in \N^+$；
• $n=\sum \limits_{i=1}^k \lambda_i$；
• $\forall 1\le i<k$，都有 $\lambda_i\ge \lambda_{i+1}$；

定义 1.2（杨图）

对于一个 $n$ 的拆分 $\lambda_{[1,k]}$，定义其对应的杨图为一个 $k$ 行的阶梯状网格图，满足第 $i$ 行有 $\lambda_i$ 个格子。

例如这是 $\lambda_{[1,8]}=\{9,9,7,3,3,3,3,1\}$ 对应的杨图：

定义 1.3.1（标准杨表）

将 $[1,n]$ 填入 $\lambda_{[1,k]}$ 对应杨图的格子中，满足每行严格递增且每列严格递增。

例如：

不难发现一个标准杨表的任意子表（选若干行若干列取交点，类比子矩阵）都是标准杨表。

定义 1.3.2（半标准杨表）

允许数字重复的杨表，满足每行不严格递增且每列严格递增。

于标准杨表相同，一个半标准杨表的任意子表都是半标准杨表。

定义 1.3.3（斜杨图）

对于 $n$ 的拆分 $\lambda_{[1,k_1]}$ 和 $m$ 的拆分 $\mu_{[1,k_2]}$，若 $k_2\le k_1$ 且 $\forall 1\le i\le k_2$ 均有 $\mu_i\le \lambda_i$，那么定义斜杨图 $\lambda/\mu$ 为 $\lambda$ 对应的杨图扣掉 $\mu$ 对应的杨图得到的网格图：

类似地，定义标准斜杨表和半标准斜杨表。

同前文，子表仍满足对应性质。

Part 2 RSK 算法和 RS 双射

RSK 算法构建了排列和有序标准杨表对间的双射——RS 双射。

算法 2.1.1（RSK 行插入算法）

对于一个标准杨表 $S$，定义插入一个未在 $S$ 中出现的数 $x$ 的算法 $S\leftarrow x$：

1. 若 $S$ 为空，则在 $S$ 中加入 $x$，插入结束；
2. 找到 $S_{1,*}$（第一行）中第一个 $> x$ 的数 $S_{1,i}$：
   • 若找不到则在 $S_{1,*}$ 右端加入 $x$，插入结束；
   • 若找到了，则用 $x$ 顶替掉 $S_{1,i}$，递归向子表 $S_{\ge 2,*}$（即删掉第一行）中行插入原来的 $S_{1,i}$；

一个例子：

对于行插入，不难发现一些性质：

• $S\leftarrow x$ 过程中顶替掉的数字的列号单调不增；
• $S\leftarrow x$ 是标准杨表；

类似地，定义列插入算法：

算法 2.1.2（RSK 列插入算法）

对于一个标准杨表 $S$，定义列插入 $x$ 算法 $x\rightarrow S$（需保证 $x$ 未在 $S$ 中出现）：

1. 若 $S$ 为空，则在 $S$ 中加入 $x$，插入结束；
2. 找到 $S_{*,1}$（第一列）中第一个 $> x$ 的数 $S_{i,1}$：
   • 若找不到则在 $S_{*,1}$ 下端加入 $x$，插入结束；
   • 若找到了，则用 $x$ 顶替掉 $S_{i,1}$，递归向子表 $S_{*,\ge 2}$（即删掉第一列）中行插入原来的 $S_{i,1}$；

其具有和行插入类似的性质。

接下来定义行删除算法：

算法 2.2.1（RSK 行删除算法）

对于一个标准杨表 $S$，定义行删除 $S_{s,t}$ 的算法，要求 $(s,t)$ 是 $S$ 的一个“边角”：

1. 令 $x=S_{s,t}$，删去格子 $(s,t)$，令当前行 $i=s-1$；
   • 若 $i=0$ 则删除结束；
   • 否则
     1. 找到 $S_{i,*}$ 中最后一个 $<x$ 的数 $S_{i,j}$，根据标准杨表的性质，这样的数必定存在；
     2. 交换 $S_{i,j}$ 和 $x$，令 $i:=i-1$，回到第一步；

一个例子：

不难发现行删除是行插入的逆操作，具体的，行删除每次替换掉的数恰好是行插入每次顶替掉的数。

类似定义列删除算法。

类似地，定义半标准杨表中的行插入和列插入算法，行插入算法不变，列插入算法仅需在顶替数字的时候更改为找到第一个 $\ge x$ 的数。而半标准杨表中的行删除或列删除算法也是类似的，显然也和对应的插入算法互逆。

接下来我们定义一个排列到标准杨表对的双射：

定义 2.1.1（RS 双射）

对于一个排列 $p_{[1,n]}$，定义标准杨表对 $(P_{p},Q_{p})$，其中 $P_p=((\dots((p_1\leftarrow p_2)\leftarrow p_3)\leftarrow\dots)\leftarrow p_n)$，即依次行插入 $p_{1},p_2,\dots,p_n$ 得到的标准杨表。而 $Q_p$ 为一个形状和 $P_p$ 相同的标准杨表，但 $Q_p$ 中 $(i,j)$ 上的数表示该格子是在第几次行插入中被创建的。

显然 $P_p$ 和 $Q_p$ 都是标准杨表。

RS 双射指出，排列 $p_{[1,n]}$ 和有序标准杨表对 $(P_p,Q_p)$ 一一对应，即有：

$n!=\sum\limits_{|S|=n}count^2(S)$

其中 $S$ 为杨图，$count(S)$ 表示该杨图对应的标准杨表个数。

证明考虑显然 $p$ 可以唯一确定 $(P_p,Q_p)$，而由于行删除是行插入的逆操作，故可以根据 $Q_p$ 记录的信息不断对 $P_p$ 执行行删除，从而求出 $p$。故该映射为双射。

Part 3 矩阵、递增坐标序列和半标准杨表

定义 3.1（递增坐标序列）

对于两个二维坐标 $(a,b),(c,d)$，定义 $(a,b)\le (c,d)$ 当且仅当 $a<c$ 或 $a=c,b\le d$（即 pair<int,int> 的比较）。

定义一个递增坐标序列 $\{(u_1,v_1),(u_2,v_2),\dots,(u_k,v_k)\}$ 需要满足 $\forall 1\le i<k$ 都有 $(u_i,v_i)\le (u_{i+1},v_{i+1})$。

不难发现排列就是 $(u_i,v_i)=(i,p_i)$ 的递增坐标序列。

对于递增坐标序列 $a$，我们可以重定义一下 RS 双射，改为 $P_a$ 由依次行插入 $v_i$ 得到，而 $Q_a$ 的格子 $(i,j)$ 上填入新增该格子对应的插入操作 $(u_i,v_i)$ 的 $u_i$：

显然 $P_a$ 和 $Q_a$ 都是半标准杨表。

那么仍然有双射 $a\leftrightarrow (P_a,Q_a)$，即递增坐标序列和半标准杨表对构成双射。

接下来，考虑定义递增坐标序列的逆：

定义 3.1.1（递增坐标序列的逆）

对于一个递增坐标序列 $a_{[1,k]}=\{(u_i,v_i)\}$，定义其逆为 $a^{-1}_{[1,k]}$ 为 $\{(v_i,u_i)\}$ 递增排序后的结果。

显然 $a^{-1}$ 也是递增坐标序列。

考虑更加形象地描述递增坐标序列和其逆。定义递增坐标序列和（无限）矩阵之间的双射：

定义 3.2（递增坐标序列和矩阵）

对于一个递增坐标序列 $a$，其对应的矩阵 $A$ 满足 $A_{i,j}$ 为 $(i,j)$ 在 $a$ 中的出现次数。

不难发现这是一个双射。

根据这个定义，不难发现 $a^{-1}$ 对应的矩阵为 $A^T$，即 $A$ 的转置。

由此，可以进一步导出一个结论：

定理 3.1

对于一个递增坐标序列 $a$，有：

$(P_a,Q_a)=(Q_{a^{-1}},P_{a^{-1}})$

证明考虑在矩阵 $A$ 上定义 $(P_A,Q_A)$ 为其对应递增坐标序列 $a=\{(u_i,v_i)\}$ 的 $(P_a,Q_a)$。

接下来先假设 $A_{i,j}\in \{0,1\}$，考虑 $P_A$ 和 $Q_A$ 的第一行，下文暂时省略下标 $A$。

注意到插入过程相当于从上到下从左往右逐个位置扫描 $A$，若扫到 $A_{i,j}=1$ 则插入 $(i,j)$。

考虑 $P_{1,1}$ 的变化，不难发现它刚开始为 $v_1$，之后每次遇到一个 $<P_{1,1}$ 的 $v_i$ 都会更新 $P_{1,1}:=v_i$，在矩阵上则形如从最高最左的 $1$ 开始往左下的一条链。而 $P_{1,2}$ 的变化也是类似的，相当于删掉 $P_{1,1}$ 对应链上的元素后递归下去。$P_{1,>2}$ 也都是类似的：

上图中红色、蓝色和绿色分别为 $P_{1,1}$、$P_{1,2}$ 和 $P_{1,3}$ 对应的链。

不妨按照时间顺序定义链的头尾，那么 $P_{1,*}$ 就是其对应链链尾 $(i,j)$ 的列坐标 $j$。

接下来考虑 $Q$ 的第一行，显然 $Q_{1,*}$ 就是 $P_{1,*}$ 对应链链头 $(i,j)$ 的行坐标 $i$。

不难发现转置后每条链都会恰好反向，即链头和链尾交换，且每个点的行列坐标互换了。所以转置后 $P_{1,*}$ 和 $Q_{1,*}$ 恰好交换了。

接下来考虑 $P_{2,*}$ 和 $Q_{2,*}$（第二行），我们首先考察哪些元素会往 $P_{\ge 2,*}$ 这个子表中插入，然后试着套用第一行的思路。

不难发现，往 $P_{\ge 2,*}$ 插入的元素一定是被从第一行顶下来的，而每条长 $k$ 的链的前 $k-1$ 个元素都会被后一个元素顶下来。具体的，对于一条链 $(u_1,v_1),(u_2,v_2),\dots,(u_k,v_k)$，被顶下去的元素为 $v_{[1,k-1]}$。

而由于 $Q$ 中记录的是插入时的 $u_i$，所以 $v_i$ 被顶下去相当于向 $(P_{\ge 2,*},Q_{\ge 2,*})$ 插入 $(u_{i+1},v_i)$，那么该链对 $(P_{\ge 2,*},Q_{\ge 2,*})$ 的影响相当于插入了 $(u_2,v_1),(u_3,v_2),\dots,(u_k,v_{k-1})$，在矩阵上表现为相邻两个点的“角落”：

那么设这些“角落”对应的矩阵为 $M$，显然 $(P_{\ge 2,*},Q_{\ge 2,*})=(P_M,Q_M)$，而 $A^T$ 对应的“角落”显然是 $M^T$，那么归纳证明即可。

而存在 $A_{i,j}>1$ 的情况也是类似的，可以通过将 $u_i$ 重标号转化为 $A_{i,j}\in\{0,1\}$ 的情况。

Part 3.1 对称矩阵和对合排列

当 $A_{i,j}=A_{j,i}$ 即 $A=A^T$ 时，我们称 $A$ 为对称矩阵。

那么显然 $P_A=Q_A$，故对称矩阵和半标准杨表构成双射。

接下来还有一个不那么显然的结论：

• $A$ 对应的每条链 $(u_1,v_1),(u_2,v_2),\dots,(u_k,v_k)$ 都是回文的；

证明较为简单。

而对合排列就是满足 $p_{p_i}=i$ 的排列，即置换环大小 $\in \{1,2\}$。显然对合排列对应的矩阵 $A$ 满足 $A=A^T$ 且其每行每列都只有一个 $1$。故对合排列和标准杨表构成双射。

那么这就导出了标准杨表个数公式：

定理 3.1.1（标准杨表个数公式）

定义大小为 $n$ 的标准杨表个数为 $f_n$，则有：

$f_n=\begin{cases}1&n=1\\2&n=2\\f_{n-1}+(n-1)f_{n-2}&n\ge 3\\\end{cases}$

这个式子相当于枚举 $n$ 是自环还是和别人配对。

Part 4 杨表与 LIS

LIS：最长上升子序列

LDS：最长下降子序列

本节仅讨论排列（元素不重复的序列）的情况，对于元素有重复的序列，可以通过重标号使得其元素不重复。

定理 4.1

一个排列 $p$ 的 LIS 长度为 $P_p$ 第一行的长度。

证明考虑 $P_p$ 第一行的变化相当于经典的使用二分 $O(n\log n)$ 求 LIS 的过程。

值得注意的是，$P_p$ 的第一行并不一定就是 $p$ 的 LIS 本身，故不能用杨表做 LIS 划分之类的问题。

引理 4.2

对于一个杨表 $S$ 和两个元素 $x,y$，有 $x\rightarrow (S\leftarrow y)=(x\rightarrow S)\leftarrow y$。

定义杨表 $S$ 的转置 $S^T$ 为交换 $S$ 的行列后得到的杨表，则 $S\leftarrow x=\left(x\rightarrow S^T\right)^T$，列插入同理。

第一点证明是简单的，考虑插入过程中顶替掉的格子形成的路径，显然行插入的路径是斜向左下的，而列插入的路径是斜向右上的，然后分讨一下 $x,y$ 间大小关系即可。

而第二点是显然的。

由此引理，我们得以导出 $P_p$ 和 $P_{p^R}$ 间的关系。

定理 4.2

对于一个排列 $p$，定义 $p^R$ 为其头尾翻转形成的排列（$p^R_i=p_{n-i+1}$）。

那么有 $P_p=P_{p_R}^T$。

注意该定理对 $Q$ 不成立。

证明考虑归纳，$|p|=2$ 时显然成立。

对于 $n=|p|>2$ 的情况，有：

$\begin{aligned} P_p&=P_{p_{[1,n-1]}}\leftarrow p_n\\ &=P^T_{p_{[1,n-1]}^R}\leftarrow p_n\\ &=\left(p_1\rightarrow P^T_{p_{[2,n-1]}^R}\right)\leftarrow p_n\\ &=p_1\rightarrow \left(P^T_{p_{[2,n-1]}^R}\leftarrow p_n\right)\\ &=p_1\rightarrow \left(P_{p_{[2,n-1]}}\leftarrow p_n\right)\\ &=p_1\rightarrow P_{p_{[2,n]}}\\ &=p_1\rightarrow P^T_{p^R_{[2,n]}}\\ &=P^T_{p^R}\\ \end{aligned}$

故成立。

该定理还有一个拓展：

定理 4.2.1（$O(n\sqrt n\log n)$ 求杨表）

定义 $p^-_i=-p_i$，$P_p=-P_{p^-}^T$。

证明方法类似。

根据这个定理，我们得以在线地快速求出一个排列 $p$ 的 $(P,Q)$。具体的，对于一个大小为 $n$ 的杨表中的格子 $(x,y)$，一定有 $x\le \sqrt n$ 或 $y\le \sqrt n$，故仅需求出其前 $\sqrt n$ 行和前 $\sqrt n$ 列再并起来即可。

前 $\sqrt n$ 行是简单的，暴力插入即可。而对于前 $\sqrt n$ 列，应用该定理后相当于插入 $-p_i$ 得到的杨表的前 $\sqrt n$ 行，故也可以维护。

那么总复杂度是 $O(n\sqrt n\log n)$ 的。

定理 4.3

一个排列 $p$ 的 LDS 长度为 $P_p$ 第一列的高度。

根据定理 4.2，$p^R$ 的 LIS 长度为 $P_p$ 第一列的高度，而显然 $p^R$ 的 LIS 是由 $p$ 的 LDS 翻转得到的，故成立。

Part 4.1 最长 k-LIS 子序列

定义 4.1.1（k-LIS 序列和 k-LDS 序列）

定义一个序列为 k-LIS 序列当且仅当其 LIS 长度不超过 $k$。

同理定义 k-LDS 序列。

显然最长 1-LIS 就是原序列的 LDS，即杨表第一列的高度。

这引导我们作出猜想：

定理 4.1.1（最长 k-LIS 子序列长度）

对于排列 $p$：

• 最长 k-LIS 子序列长度为 $P_p$ 前 $k$ 列的高度和；

• 最长 k-LDS 子序列长度为 $P_p$ 前 $k$ 行的长度和；

懒得证了，感性理解一下，去看论文吧。

例题：P3774 [CTSC2017] 最长上升子序列

Part 5 钩子公式

接下来回答一个一直悬而未决的问题：

对于一个大小为 $n$ 的杨图 $\lambda$，其有多少个对应的标准杨表？

定理 5.1（钩子公式）

对于一个杨图 $S$，定义 $h_{(i,j)}$ 为 $S_{i,j}$ 右方的格子的个数加上其下方的格子的个数再 $+1$ 的值（$(i,>j)+(>i,j)+(i,j)$，形如一个钩子），则该 $S$ 对应的标准杨表共有 $\frac{n!}{\prod h_{(i,j)}}$ 种。

证明 5.1（钩子公式）

考虑归纳。

$n=1$ 时显然成立，现在假设对于 $[1,n-1]$ 均成立，来证明对于 $n$ 成立。

显然 $n$ 填入的位置一定是“边角”，并且一个杨图挖掉边角后还是杨图。

那么设 $X_i=(a_i,b_i)$ 为 $\lambda$ 从上往下第 $i$ 个边角的位置，$\mu^{(i)}$ 为 $\lambda$ 挖掉 $X_i$ 后得到的 $n-1$ 的杨图，则我们要证明：（$m$ 是边角的个数）

$\frac{n!}{\prod h^\lambda_{(i,j)}}=\sum\limits_{i=1}^m\frac{(n-1)!}{\prod h^{\mu^{(i)}}_{(i,j)}}$

也即：

$\sum\limits_{i=1}^m\frac{\prod h^\lambda_{(i,j)}}{\prod h^{\mu^{(i)}}_{(i,j)}}=n$

接下来，我们只考虑 $\lambda$ 的杨图。定义 $ct_{(i,j)}=i-j$，并且对于 $i\in [0,m]$ 定义 $Y_i=(a_i,b_{i+1})$，并定义 $a_0=b_0=b_{m+1}=0$，$X_0=(0,0)$：

再令 $D_{(i,j)}$ 和 $R_{(i,j)}$ 为从 $(i,j)$ 开始不停往下走和往右走最终到达的格子，那么有 $h_{(i,j)}=ct_{D_{(i,j)}}-ct_{R_{(i,j)}}+1$。

令 $x_{i}=ct_{X_i},y_i=ct_{Y_i}$，则有：

$\sum\limits_{i=0}^m x_i=\sum\limits_{i=0}^m y_i$

这是因为 $x_i=a_i-b_i,y_i=a_i-b_{i+1}$，$b$ 错位抵消后仅剩 $b_{m+1}-b_0=0$。

接下来考虑证明：

$\sum\limits_{i=1}^m\frac{\prod h^\lambda_{(i,j)}}{\prod h^{\mu^{(i)}}_{(i,j)}}=-\sum\limits_{i=1}^m\frac{\prod\limits_{j=0}^m(x_i-y_j)}{\prod\limits_{j=1,j\not=i}^m(x_i-x_j)}$

证明

考虑添加边角 $X_i$ 的影响 $\frac{\prod h^\lambda_{(i,j)}}{\prod h^{\mu^{(i)}}_{(i,j)}}$，显然只会影响到 $(a_i,*)$ 和 $(b_i,*)$。

对于同一列的影响，实际上只有 $L_j=(a_j,b_i)$（$1\le j<i$）和 $M_j=(a_j+1,b_i)$（$0\le j<i$）这些格子对这个分数有贡献：（其它的都会错位相消）

更具体的，只有 $M_j$ 会对分子造成影响，且只有 $L_j$ 会对分母造成影响。

注意到：（考虑 $X_i$ 和 $Y_i$ 的位置）

$h^{\lambda}_{M_j}=h^{\lambda}_{(a_j+1,b_i)}=ct_{D_{(a_j+1,b_i)}}-ct_{R_{(a_j+1,b_i)}}+1=x_i-y_j\\ h^{\mu^{(i)}}_{L_j}=h^{\lambda}_{(a_j,b_i)}-1=ct_{D_{(a_j,b_i)}}-ct_{R_{(a_j,b_i)}}=x_i-x_j\\$

相似的，对于同一行的影响，有 $L_j=(a_i,b_j)$（$i< j\le m$），$M_j=(a_i,b_{j+1}+1)$（$i\le j\le m$），且：

$h^{\lambda}_{M_j}=y_j-x_i\\ h^{\mu^{(i)}}_{L_j}=x_j-x_i\\$

那么有：

$\begin{aligned} \frac{\prod h^\lambda_{(i,j)}}{\prod h^{\mu^{(i)}}_{(i,j)}}&=\frac{\prod\limits h^{\lambda}_{M_j}}{\prod h^{\mu(i)}_{L_j}}\\ &=\frac{\prod\limits_{0\le j<i} (x_i-y_j)\prod\limits_{i\le j\le m}(y_j-x_i)}{\prod\limits_{1\le j<i}(x_i-x_j)\prod\limits_{i<j\le m}(x_j-x_i)}\\ &=-\frac{\prod\limits_{j=0}^m(x_i-y_j)}{\prod\limits_{j=1,j\not=i}^m(x_i-x_j)} \end{aligned}$

证毕。

然后我们将证明：

$-\sum\limits_{i=1}^m\frac{\prod\limits_{j=0}^m(x_i-y_j)}{\prod\limits_{j=1,j\not=i}^m(x_i-x_j)}=-\frac{1}{2}\sum\limits_{i=0}^m x_i^2-y_i^2$

证明

注意到这个式子很像拉插，所以不妨设：（不知道怎么想到的）

$P(t)=-\sum\limits_{i=1}^m\frac{\prod\limits_{j=0}^m(x_i-y_j)}{\prod\limits_{j=1,j\not=i}^m(x_i-x_j)}\prod\limits_{j=1,j\not=i}^m (t-x_j)\\ Q(t)=\prod\limits_{i=0}^m(t-y_i)$

那么 $P(t)$ 是 $m-1$ 次多项式，$Q(t)$ 是 $m+1$ 次多项式，我们要求的值就是 $[t^{m-1}]P(t)$。

注意到 $P(t)+Q(t)$ 在 $t=x_i$（$i\not=0$）时为 $0$，且 $x_i$ 互不相同（每斜行恰好有一个边角），且 $[t^{m+1}](P(t)+Q(t))=1$，故存在 $\alpha$ 使得：

$P(t)+Q(t)=(t+\alpha)\prod\limits_{i=1}^m(t-x_i)$

那么：

$\begin{aligned} P(t)&=(t+\alpha)\prod\limits_{i=1}^m(t-x_i)-\prod\limits_{i=0}^m(t-y_i)\\ &=\left(\alpha-\sum\limits_{i=1}^m x_i+\sum\limits_{i=0}^m y_i\right)t^m+\left(-\alpha\sum\limits_{i=1}^mx_i+\sum\limits_{1\le i<j\le m}x_ix_j-\sum\limits_{0\le i<j\le m}y_iy_j\right)t^{m-1}+\dots \end{aligned}$

根据之前的结论，有：

$\sum\limits_{i=0}^m x_i=\sum\limits_{i=0}^m y_i$

且 $x_0=0$，那么 $\sum\limits_{i=0}^m y_i-\sum\limits_{i=1}^m x_i=0$，所以 $\alpha=0$。

故 $[t^{m-1}]P(t)=\sum\limits_{1\le i<j\le m}x_ix_j-\sum\limits_{0\le i<j\le m}y_iy_j=\sum\limits_{0\le i<j\le m}x_ix_j-y_iy_j$。

继续：

$\begin{aligned} \sum\limits_{0\le i<j\le m}x_ix_j-y_iy_j&=\frac{1}{2}\left(\left(\sum\limits_{i=0}^m x_i\right)^2-\sum\limits_{i=0}^m x_i^2-\left(\sum\limits_{i=0}^m y_i\right)^2+\sum\limits_{i=0}^m y_i^2\right)\\ &=\frac{1}{2}\sum\limits_{i=0}^{m}y_i^2-x_i^2\\ &=-\frac{1}{2}\sum\limits_{i=0}^{m}x_i^2-y_i^2\\ \end{aligned}$

证毕。

那么代入 $x_i=a_i-b_i$ 和 $y_i=a_i-b_{i+1}$，有：

$\begin{aligned} -\frac{1}{2}\sum\limits_{i=0}^{m}x_i^2-y_i^2&=-\frac{1}{2}\sum\limits_{i=0}^m(a_i-b_i)^2-(a_i-b_{i+1})^2\\ &=-\frac{1}{2}\sum\limits_{i=0}^m a_i^2-2a_ib_i+b_i^2-a_i^2-b_{i+1}^2+2a_ib_{i+1}\\ &=-\frac{1}{2}\sum\limits_{i=0}^m -2a_ib_i+b_i^2+2a_ib_{i+1}-b_{i+1}^2\\ &=-\frac{1}{2}\left(b_0^2-b_{m+1}^2+\sum\limits_{i=0}^m2a_i(b_{i+1}-b_i)\right)\\ &=\sum\limits_{i=0}^m a_ib_{i+1}-a_ib_i \end{aligned}$

注意到这个实际上相当于将杨图竖着划分成很多个长方形加起来，结果就是杨图的面积，故：

$n=\sum\limits_{i=0}^m a_ib_{i+1}-a_ib_i$

即证毕。