《Bijective Proof Probs》P16 的另一种证法

题意

\([3-]\) 给定 \(n\geq 0\)，那么

其中 \(i,j,k\in \mathbb{N}\)。

解答

我们先证明一个引理：给定任意一个 0 和 1 个数相同的 01 串，有且仅有一种方法将其分为三段（每段可以为空），且满足：

• 第一段 1 的个数等于第二段 0 的个数（记为【甲】）；
• 第二段 1 的个数等于第三段 0 的个数（记为【乙】）；
• 第三段 1 的个数等于第一段 0 的个数（记为【丙】）；
• 第二段以 0 开头或第三段以 1 开头（记为【丁】）。

证明：我们假设第 \(i\) 段 0 的个数为 \(a_i\)，1 的个数分别为 \(b_i\)。显然我们满足了 \(b_1=a_2,b_3=a_1\)（即【甲】、【乙】）就能满足 \(b_2=a_3\)（即【丙】）。我们先将一、二段的分割点放在最左边（记为 \(p\)），将二、三段的分割点放在最右边（记为 \(q\)）；每一时刻，我们按照如下规则移动 \(p\) 和（或）\(q\)，直到 \(p,q\) 重叠：

• 若 \(p\) 右侧为 0；
  • 若 \(q\) 左侧为 1，那么 \(p\) 右移一格，\(q\) 左移一格；
  • 若 \(q\) 左侧为 0，那么 \(q\) 左移一格；
• 若 \(p\) 右侧为 1，那么 \(p\) 右移一格。

可以发现整个过程始终符合【甲】和【丁】，且包括了所有同时满足【甲】和【丁】的分割方案。又注意到每个时刻 \(a_2-b_1\) 会减少一，初始 \(a_2-b_1\geq 0\)，结束时 \(a_2-b_1\leq 0\)，因此有且仅有一个时刻同时满足【甲】【乙】【丁】，其也满足【丙】。QED。

此处再举例说明一下：

p 1 . 1 . 0 . 0 . 1 . 0 . 1 . 0 q   此时 a_2-b_1=4
. 1 p 1 . 0 . 0 . 1 . 0 . 1 . 0 q   此时 a_2-b_1=3
. 1 . 1 p 0 . 0 . 1 . 0 . 1 . 0 q   此时 a_2-b_1=2
. 1 . 1 p 0 . 0 . 1 . 0 . 1 q 0 .   此时 a_2-b_1=1
. 1 . 1 . 0 p 0 . 1 . 0 q 1 . 0 .   此时 a_2-b_1=0，合法
. 1 . 1 . 0 p 0 . 1 q 0 . 1 . 0 .   此时 a_2-b_1=-1
. 1 . 1 . 0 . 0p/q1 . 0 . 1 . 0 .   此时 a_2-b_1=-2

下面我们为左右两侧赋予组合意义：

• 左侧：将 \(2n\) 分为 \(x+y+z\)，构造三段长度各为 \(x,y,z\) 的 01 序列，满足【甲】【乙】【丙】；
• 右侧：任意一个长度不超过 \(2n\) 的、0 与 1 个数相等的 01 串。

接着构造双射：

• 左侧 -> 右侧：若第二段以 1 开头、第三段以 0 开头，则各将这两段各删除开头一个字符。重复如上过程。最后将三个串拼接起来；
• 右侧 -> 左侧：根据引理所述方式，将串分为三段，并通过同时在第二段首补 1、在第三段首补 0 来使三段的长度和达到 \(2n\)。

《Bijective Proof Probs》P16 的另一种证法

原文：https://www.cnblogs.com/wallbreaker5th/p/14735917.html