你知道吗？连分数

而连分数

? ???

这两个连分数的分子竟然是相同的！这是为什么呢？《Proofs that Really Count》里边给出了一个有意思的组合学解说。

为了叙说便利，接下来咱们统一用下图所示的符号来标明连分数：

??

咱们用 p(a1, a2, a3, …, an) 来标明 [a1, a2, a3, …, an] 的最简分数方法的分子，用 q(a1, a2, a3, …, an) 来标明 [a1, a2, a3, …, an] 的最简分数方法的分母。所以，咱们有

注意到，最终的那个分数现已是最简的了。假设不是的话，这就意味着 p(a2, a3, …, an) 和 a1 · p(a2, a3, …, an) + q(a2, a3, …, an) 之间有公共的因数，这进一步标明 p(a2, a3, …, an) 和 q(a2, a3, …, an) 之间有必要要有公共的因数；但是 p(a2, a3, …, an) 和 q(a2, a3, …, an) 是 [a2, a3, …, an] 的最简分数方法的分子和分母，它们现已没有公共的因数了。

因此，连分数的分母就应该满意

? ???q(a1, a2, a3, …, an) = p(a2, a3, …, an)

而连分数的分子则应该满意

? ?? ???p(a1, a2, a3, …, an)

? ???= a1 · p(a2, a3, …, an) + q(a2, a3, …, an)

? ???= a1 · p(a2, a3, …, an) + p(a3, …, an)

? ?再结合初始条件 p(an) = an 以及 p(an-1, an) = an-1 · an + 1 ，咱们就得到了连分数分子的一个完好的递推公式。接下来，咱们要为这个递推公式赋予一个组合数学上的含义。考虑一个 n × 1 的棋盘，你能够在这个棋盘上放置一些 1 × 1 的砖块或许 2 × 1 的砖块。 1 × 1 的砖块能够叠放起来，但第 i 个方位上的砖块数目不能超过 ai； 2 × 1 的砖块则只能独自放置，它的上面和下面都不能有任何其他砖块。咱们规则，棋盘的每个方位上都有必要放有砖块，不允许呈现任何空的方位。假设 n = 6 ，并且 a1 到 a6 的值依次是 3, 1, 4, 1, 5, 9 ，那么咱们的棋盘就如左图所示，右图则是一个合法的砖块放置计划。

? ???给定 n 的值以及序列 a1, a2, …, an 后，怎么核算满意要求的砖块放置计划数呢？咱们能够尝试着选用递推的方法。咱们能够把一切的计划分为两大类。其间一个大类便是，第一个方位放有 1 到 a1 个 1 × 1 的砖块，这类计划的总数等于 a1 乘以在后面 n - 1 个方位放置砖块的计划数；另一个大类则是，第一个方位被一个 2 × 1 的砖块所掩盖，这类计划的总数就直接等于在后面 n - 2 个方位放置砖块的计划数。你会发现，这个组合问题的递推公式与方才的 p(a1, a2, …, an) 完全一致，并且简单验证，只在第 n 个方位放砖块有 an 种方法，只在第 n - 1 和第 n 个方位放砖块则有 an-1 · an + 1 种方法，这也与 p(an) 和 p(an-1, an) 的值是相符的。因此， p(a1, a2, …, an) 的值正好便是在高度限制分别为 a1, a2, …, an 的棋盘上放置砖块的计划总数！

? ?回到本文开始的问题：为什么连分数 [a1, a2, a3, …, an] 和 [an, …, a3, a2, a1] 的分子是相同的呢？现在看来几乎是明显的：由于这两个连分数的分子标明的是两个左右镜像的棋盘的砖块放置计划数，而两个左右镜像的棋盘本质上是相同的，它们的砖块放置计划数明显应该持平。

??转自 辛几许&李代数? ?? ?早年有个数
金融工程, 数学算法