「co-examination - A」

破壁，组合意义法：

五种颜色 \(\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. 对上了。

呃呃呃，组合恒等式法。