常见组合恒等式

令 \(m\le n\)。

• 对称性：\(n,m\ge 0\) 时，\(\binom{n}{m}=\binom{n}{n-m}\)。

• 单行和：\(\sum\limits_{i=0}^n \binom{n}{i} = 2^n, \sum\limits_{i=0}^n (-1)^i\binom{n}{i}=0, \sum\limits_{i=0}^n i\binom{n}{i}=n2^{n-1}\)。

• 从 \((n,m)\) 往左上的斜线和：\(\sum\limits_{i=0}^m \binom{n-i}{m-i}=\binom{n+1}{m}\)。

• 从 \((n,0)\) 往右下的长为 \(m\) 斜线： \(\sum\limits_{i=0}^m \binom{n+i}{i}=\binom{n+m+1}{m}\)。

• 从 \((n,k)\) 往右下的长为 \(m\) 斜线：\(\sum\limits_{i=0}^m \binom{n+i}{k+i} = \binom{n+m+1}{m+k} - \binom{n}{k-1}\)。

• 从 \((n,0)\) 往右上的斜线和： \(\sum\limits_{i=0}^n \binom{n-i}{i}=F_{n+1}\)。

• 上指标反转：\(\binom{n}{m} = (-1)^m \binom{m-n-1}{m}\)。

• 范德蒙德卷积：\(\sum\limits_{i=0}^k \binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}\)。

• 上指标范德蒙德卷积：\(\sum\limits_{i=-b}^a \binom{a-i}{n}\binom{b+i}{m} = \binom{a+b+1}{n+m+1}\)。

• 卡特兰数：\(H_0 = 1, H_n = \sum\limits_{i=0}^{n-1} H_{i} H_{n-1-i}\)，令 \(S(n,m)=\sum\limits_{i=0}^m H_iH_{n-i}\)，则 \(S(n,m) = H_{n+1} - S(n,n-m-1)\)。

• 卡特兰数自卷积：\([x^n ]H^m(x)=\binom{2n+m-1}{n+m-1}-\binom{2n+m-1}{n+m}\)。

• 从 \((0,0)\) 到 \((n,m)\) 不碰到 \(y=x+l\) 和 \(y=x+r\) 的格路计数：\(\sum\limits_{k\in \Z} \binom{n+m}{n-k(r-l)}-\binom{n+m}{n-k(r-l)+r}\)。