Classical Fibonacci compositions

技术摘要：经典斐波那契组合

问题陈述
本文研究了三种不同类型的受限整数组合，其计数结果与斐波那契数列（$F_n$）相匹配。虽然整数 $n$ 的一般组合数为已知的 $2^{n-1}$，但本研究侧重于由特定部分约束定义的子集：

1. 音律组合 ($C_{12}(n)$)： 部件限制在集合 $\{1, 2\}$ 中的 $n$ 的组合。该模型源于古代印度音律学（特别是关于诗歌格律中长短音节计数的皮平加拉 [Piṅgala] 及后世学者的著作）。
2. 奇数部分组合 ($C_o(n)$)： 所有部件均为奇整数的 $n$ 的组合。此类组合曾由 19 世纪英国的奥古斯塔斯·德·摩根（Augustus De Morgan）进行过分析。
3. 大部组合 ($\hat{C}_1(n)$)： 所有部件均至少为 2 的 $n$ 的组合。此类组合由亚瑟·凯莱（Arthur Cayley）于 1876 年提出。
   本文旨在为这些集合的计数提供组合证明，并通过平铺论证（tiling arguments）展示它们如何满足斐波那契递推关系（$F_n = F_{n-1} + F_{n-2}$）。

方法论
主要采用的方法论是通过平铺论证进行的组合证明。作者将 $n$ 的一个组合建模为对 $1 \times n$ 板块的平铺：

• 一个大小为 $k$ 的部分对应一个 $1 \times k$ 的平铺块。
• 部分序列对应平铺块的排列。
• 切割/合并序列（Cut/Join Sequences）： 作者利用珀西·麦克马洪（Percy MacMahon）的概念，将组合表示为 $n$ 个单元格之间“切割”（C）和“合并”（J）选择的二元序列。
• 双射（Bijections）： 证明的核心在于建立 $n$ 的组合集合与 $n-1$ 和 $n-2$ 的组合集合之并集的显式双射。这种结构分解直接反映了斐波那契递推关系。
• 共轭（Conjugation）： 本文采用了麦克马洪关于“共轭组合”的概念，即通过反转组合的切割/合并序列（交换 C 和 J）来生成一个新的组合。这一操作是最终定理的核心。

主要贡献与结果

1. 音律组合的计数 ($C_{12}(n)$)：

   • 结果： $c_{12}(n) = F_{n+1}$。
   • 证明： 在 $C_{12}(n)$ 与 $C_{12}(n-1) \cup C_{12}(n-2)$ 之间建立了双射。通过附加一个长度为 2 的部分（一个多米诺骨牌）将 $C_{12}(n-2)$ 中的组合映射到 $C_{12}(n)$；通过附加一个长度为 1 的部分（一个正方形）将 $C_{12}(n-1)$ 中的组合进行映射。区别在于所得组合的最后一个部分。

2. 奇数部分组合的计数 ($C_o(n)$)：

   • 结果： $c_o(n) = F_n$。
   • 证明： 一个双射将 $C_o(n-2)$ 映射到 $C_o(n)$，方法是将最后一个部分 $k$ 增加到 $k+2$（保持奇数性），并将 $C_o(n-1)$ 映射到 $C_o(n)$，方法是附加一个长度为 1 的部分。这两个集合通过最后一个部分是 1 还是 $\ge 3$ 来进行区分。

3. 大部组合的计数 ($\hat{C}_1(n)$)：

   • 结果： 对于 $n \ge 2$，$\hat{c}_1(n) = F_{n-1}$。
   • 证明： 一个双射将 $\hat{C}_1(n-2)$ 映射到 $\hat{C}_1(n)$，方法是附加一个长度为 2 的部分；并将 $\hat{C}_1(n-1)$ 映射到 $\hat{C}_1(n)$，方法是将最后一个部分 $k$ 增加到 $k+1$。区别在于最后一个部分是恰好为 2 还是 $\ge 3$。

4. 通过共轭进行的综合（定理 4）：

   • 结果： 对于 $n \ge 2$，存在双射 $C_{12}(n) \cong \hat{C}_1(n) \cup C_o(n)$。
   • 意义： 该结果通过展示部件为 $\{1, 2\}$ 的组合集合可以通过特定的映射（涉及共轭）被划分为部件 $\ge 2$ 的组合集合和具有奇数部分的组合集合，从而为恒等式 $F_{n+1} = F_n + F_{n-1}$ 提供了一个直接的组合实现。
   • 机制： 证明利用了麦克马洪的共轭法。对于 $\hat{C}_1(n)$ 中的一个组合，其共轭组合没有相邻的“合并”项（没有大于 2 的部分）且以 1 开始/结束；移除这些边界 1 并附加一个 2 即可得到 $C_{12}(n)$ 中的一个元素。对于 $C_o(n)$，奇数部分被扩展为由 2 和一个最后的 1 组成的序列。

重要性与主张
本文声称为广为人知的计数结果提供了严谨的组合证明，将古代印度音律学与 19 世纪英国数学联系起来。作者强调，虽然数值结果（$c_{12}(n) = F_{n+1}$ 等）是已知的，但使用平铺和共轭进行的双射证明提供了证明斐波那契恒等式的独特工具。

作者指出，不同的组合类型为证明特定的恒等式（例如偶数或奇数下标斐波那契数之和）提供了不同程度的便利性。文章最后谦虚地指出，定理 4 中的双射（连接 $C_{12}$、$\hat{C}_1$ 和 $C_o$）可能是一项新颖的贡献，通过受限整数组合的角度，为递推关系 $F_{n+1} = F_n + F_{n-1}$ 提供了一个统一的组合框架。这项工作是作为组合证明斐波那契恒等式的资源，并引用了作者本人的著作以及 Benjamin 和 Quinn 的工作作为背景。