破壁,组合意义法:
五种颜色 $\star,a,b,c,d$。
- 对于 l.h.s.
钦定 $k$,在 $3n+k$ 个球中选出 $2n$ 个球染色,在靠左的 $n$ 个球中选 $k$ 个染成 $a$ 色,剩余 $n-k$ 个 $b$ 色;在靠有的 $n$ 个球中选 $k$ 个染成 $c$ 色,剩余 $n-k$ 个 $d$ 色。
- 对于 r.h.s.
有 $3n$ 个 $\star$ 色球,钦定其中 $n$ 个,再拿出一个全 $0$ 序列,选出 $n$ 个赋值为 $1$,此时已经为右式的组合意义了,我们考虑把左右式对起来。
拿出两个指针 p
和 q
,分别指向为 $3n$ 个 $\star$ 色球中的未钦定球,和 $0/1$ 序列,两指针同步移动。
当 q
碰到 $1$,把 p
所指的球染成 $b$ 色,当 p
之前有恰好 $n$ 个「钦定或 $b$ 色」球时停下。那么此时设 p
前面有 $k$ 个钦定球,$n-k$ 个 $b$ 色球,p
后面有 $o$ 个球,那么 q
后面还有 $o+k$ 个数,其中恰好有 $k$ 个 $1$。
把 p
后面的球放在 q
之后 $0$ 的位置上,把 $1$ 的位置染成 $d$ 色,把 p
前的球和这个拼起来就和 l.h.s. 对上了。
呃呃呃,组合恒等式法。