林奕含高二时和小伙伴何念青的研究《穿越網格愛上你》，曾在2008年台湾国际科学展览会上获得高中组数学第一名。

在研究报告的开头，林奕含这样介绍自己:

我叫林奕含，現在就讀台南女中數理資優班二年級，從小便對數學有濃厚的興趣，喜歡向各
式各樣的題目挑戰，也參加過許多數學競試。除此之外，課餘時間喜歡閱讀課外讀物的我，
對文學也頗有研究，常代表班上甚至學校參加作文和演講比賽。

源起

这个研究题目的来源，是2005年普特南数学竞赛的第二题：

即$n \times 3$的网格上从点$(1,1)$到点$(n,1)$的哈密顿路径的计数问题。

即$n \times 3$的网格上从点$(1,1)$到点$(n,1)$的哈密顿路径的计数问题。

答案是$2^{n-2}$: 符合条件的哈密顿路径，与$\{1,\ldots, n\}$的包含$n$且有偶数个元素的子集一一对应。这样的子集的个数，即为$\{1, \ldots, n-1\}$的含有奇数个元素的子集个数。根据二项式系数的性质，为$2^{n-2}$个。

推广

上述普特南题目是$n\times k$网格从$(1,1)$到$(n,1)$哈密顿路径计数问题的的$k=3$特例。林奕含与何念青的研究，则讨论了$k=4$时的情况。

生成函数解法

搜索哈密顿路径计数问题，搜到一篇1997年发表的论文The number of Hamiltonian paths in a rectangular grid。这篇文章给出了$k=1,2,3,4,5$时的解法，尤其是$k=4$与$k=5$时的生成函数。这个解法相对更简洁一些。

这篇文章同时覆盖了从$(1,1)$到$(n,1)$(左下角到右下角)的哈密顿路径计数问题和从$(1,1)$到$(n,k)$(左下角到右上角)的哈密顿路径计数问题。前者记为$f(k,n)$，后者记为$g(k,n)$。

路径记法

文章中引入了一种表示格点哈密顿路径的方法：

假设路径是有向的，并且在终点和$(1,1)$间引入辅助线构成哈密顿回路，则整个路径将二维平面分为内外两部分。将内部的格子标记为1，外部的格子标记为0，则每一列的0和1构成二进制表示。

例子:

#以下路径表示为3(11), 0(00), 3(11), 2(10)
* - *   * - * - *
| 1 | 0 | 1   1 |
*   *   *   * - *
| 1 | 0 | 1 | 0
*   * - *   * - *

$k=3$

下面以$n=2,3,4$为例举例观察递推关系。

f(3,2) = 1
* - *
| 1
* - *
  0 |
* - *

g(3,2) = 1
* - *
| 1 |
*   *
| 1 |
*   *

f(3,3) = g(3,2) + f(3,2) = 2
* - *   *        * - * - * 
| 1 | 0 |        | 1   1
*   *   *        * - * - *
| 1 | 0 |          0   0 |
*   * - *        * - * - *

g(3,3) = f(3,2) + g(3,2) = 2
* - * - *        * - * - *       
| 1   1 |        | 1   1 |         
*   * - *        * - *   *       
| 1 | 0            0 | 1 |       
*   * - *        * - *   *       

f(3,4) = g(3,3) + f(3,3) = 4
* - *   * - *    * - * - *   *
| 1 | 0 | 1      | 1   1 | 0 |
*   *   * - *    *   * - *   *
| 1 | 0   0 |    | 1 | 0   0 |
*   * - * - *    *   * - * - *

* - * - *   *    * - * - * - *
| 1   1 | 0 |    | 1   1   1   
* - *   *   *    * - * - * - *
  0 | 1 | 0 |      0   0   0 |
* - *	* - *    * - * - * - *

g(3,4) = f(3,3) + g(3,3) = 4
* - *   * - *    * - * - * - *    
| 1 | 0 | 1 |    | 1   1   1 |
*   *   *   *    *   * - * - *
| 1 | 0 | 1 |    | 1 | 0   0
*   * - *   *    *   * - * - *

* - * - * - *    * - * - * - *
| 1   1   1 |    | 1   1   1 |
* - *   * - *    * - * - *   *
  0 | 1 | 0        0   0 | 1 |
* - *   * - *    * - * - *   *

当$k=3$时，$f(3,n)$与$g(3,n)$之间的递推关系是: \begin{align} f(3,n) &= g(3, n-1) + f(3, n-1) \\ g(3,n) &= f(3, n-1) + g(3, n-1) \\ f(3,1) &= 1\\ g(3,1) &= 0\\ \end{align}

可以解得 $f(3,n)$的生成函数$F(3,x) = \frac{(x^2-x)}{2x-1}$

$g(3,n)$的生成函数$G(3,x) = \frac{x^2}{1-2x}$

根据生成函数性质可以反推(取生成函数多项式相应项的系数)当$n\neq 1$时， $f(3,n) = 2^{n-2}$ 以及$g(3,n) = 2^{n-2}$

$k=4$

和$k=3$类似，但是情形更复杂。

  • 第一列数字为7: 左下到右上 $g(4,n-1)$, 左下到右下$f(4,n-1)$

    * - * 
| 1
*   *
| 1 
*   *
| 1 
*   *

  • 第一列数字为5

    • (5,4): 左下到右上 $f(4,n-2)$, 左下到右下$g(4,n-2)$
    * - * - *
| 1   1
* - * - *
  0   0
* - *   *
| 1 | 0
*   * - *

  • 第一列数字为6, 用$f_6(4,n)$和$g_6(4,n)$表示第一列数字为6时的计数

    • (6,2,6): 左下到右上 $f_6(4,n-2)$, 左下到右下$g_6(4,n-2)$
    * - *   * - *
| 1 | 0 | 1
*   * - *   *
| 1   1   1
* - * - * - *
  0   0   0
* - * - * - *
    • (6,2,7): 左下到右上 $g(4,n-3)$, 左下到右下$f(4,n-3)$
    * - *   * - *
| 1 | 0 | 1
*   * - *   *
| 1   1   1
* - * - *   *
  0   0 | 1
* - * - *   *
    • (6,3,6): 左下到右上 $g(4,n-3)$, 左下到右下$f(4,n-3)$
    * - *   * - *
| 1 | 0 | 1
*   * - *   *
| 1   1   1
* - *   * - *
  0 | 1 | 0
* - *   * - *
    • (6,4): 左下到右上 $f(4,n-2)$, 左下到右下$g(4,n-2)$
    * - * - *
| 1   1
*   * - *
| 1 | 0
* - *   *
  0   0
* - * - *

可得 \begin{align} f(4,n) &= g(4, n-1) + f(4, n-2) + f_6(4,n) \\ g(4,n) &= f(4, n-1) + g(4, n-2) + g_6(4,n) \\ f_6(4,n) &= f(4,n-2) + 2g(4,n-3) + f_6(4,n-2) \\ g_6(4,n) &= g(4,n-2) + 2f(4,n-3) + g_6(4,n-2) \\ f(4,1) &= g(4,2) = 1\\ g(4,1) &= f(4,2) = 0\\ f_6(4,2) &=g_6(4,2)=g_6(4,3)=0\\ f_6(4,3) &=2\\ \end{align}

可以解得$f,g,f_6,g_6$的相应生成函数