一个结论的组合意义证明

_LHF_ · 2021-08-21 20:57:52 · 个人记录

左边的式子的组合意义：

枚举 k，从 3n+k 个球中选出 2n 个球，左边 n 个中选出 k 个染成深蓝色，其他染成浅蓝色。右边 n 个中选出 n-k 个染成深绿色，其他染成浅绿色。

右式我们可以拿出 3n 个球，其中 n 做一个标记。再生成一个长度为 3n 的 01 序列，其中有 n 个 1。

然后我们对于所有没有标记的球按顺序拿出，然后一起移动。第一个指针每一次移动到下一个没有标记的球，第二个指针每一次向右移动一位。

然后两个指针指到初始的情况，并同时开始移动。如果第二个指针指到的位置为 1，那么把这个球染成浅蓝色，并将在第一个指针前的被标记的球染成深蓝色。直到指针前一共有 n 个球染色，得到第一段球。

于是就一共有 k 个浅蓝色的球和 n-k 个深蓝色的球。

假设第一个指针后面总共还剩下 x 个球，那么第二个指针后面还剩下 n-k 个 1，第二个指针后面还有 x 个 0。

对于是 0 的位置，我们依次将第一个指针后面的球放在 0 的位置，如果这个球有标记，那么染成深绿色，然后在 1 的位置放上浅绿色的球，得到第二段球。

两段球拼接起来即为左式。