含对角线的n阶棋盘计数问题分析

【摘要】提出了含对角线n阶棋盘的计数问题，利用问题解的性质，采用两种思路求解，将问题等价转化为求某一函数的Taylor展开式中第n+1项的系数．

【关键词】计数原理；幂级数；Taylor展开；级数运算

1 问题叙述

如图1所示，考虑一加对角线的棋盘，对角线上的点依次为，从到每步只能向右、向上走单位长度，或在时沿走到，并称满足这种条件的路径为可行路径.易知每条可行路径最多走步，若两条可行路径的步数不同或者在某一步走法不同，则说它们是不同的可行路径.如图所示的三条路径均是可行路径.

2 预备知识与符号约定

引理1 上文所述棋盘中，从到不经过任一线段的可行路径有种.

引理2 时，上文所述棋盘中，从到不经过点集的可行路径有种.

这里不对上述两条引理加以证明，读者可参考文献[1].

定义1 记加对角线的n阶棋盘的所有可行路径数为.约定.并记

定义2 时，记不经过点集的可行路径为，由引理2知.约定.

3 问题求解

定理1 .

证明：给定一条可行路径，它或者不经过对角线，或者经过至少某条线段.若它不经过对角线，此时由引理1知有种走法；若经过，设第一次经过的线段为，则该路径不经过，由引理1知从到有，而从到有种走法，故由乘法原理知有种走法.再由加法原理知总共有种走法.证毕.

定理2 .

证明：由定义2知

再由定理1有，.

定理3 .

证明：由Taylor展开有

令即得结论.

由定理2及可知，即.再由定理3，代入我们得到

定理4 .

下面将给出另一种求表达式的思路.

定理5 ，其中，即.

证明：给定一条可行路径：若路径不经过点集，则有种走法；若路径经过中至少一点且第一次经过的点为，则从到有种走法，从到有种走法；若路径经过中至少一点且第一次经过的点为，则从到有种走法，到有种走法；由加法原理和乘法原理得.证毕.

定理6 ，其中.

证明：，由定理5知

，证毕.

定理7 .

证明：由Taylor展开可知，令即得证.

由定理6可知，由定理7代入可得，结论与定理4一致.

下面我们求的幂级数展开，进而其幂级数展开的的系数即为所求问题的解.求解如下：

，记，注意到，，故，记，则，而，故

，

考虑上式右端的系数即得

定理8 ，其中，，.

定理8已给出的求解公式，但一项计算量依旧较大，可以进一步研究求解的显式表示，有兴趣的读者可以加以探究.下面给出时的值：

1 2 3 4 5 6 7 8 9

3 11 43 173 707 2917 12111 50503 211263

例1 如图2所示为一个的棋盘，是由一个的棋盘与一个加对角线的棋盘拼接而成，其相交部分为线段，线段由下至上依次为点.记从到的所有可行路径数为，对于给定的一条可行路径，其必经过某个.假设最小的值为，则该路径必是从的左边到达（若是从到达则与假设矛盾），依引理1知从到有种走法，从到有种走法，由计数原理知.约定，.下表给出部分的取值：

0 1 2 3 4 5 6 7 8 9

0 1 1 1 1 1 1 1 1 1 1

1 3 4 5 6 7 8 9 10 11 12

2 11 16 22 29 37 46 56 67 79 92

3 43 65 94 131 177 233 300 379 471 577

4 173 808 1108 1487 1958 2535 3233 4068 5057 6218

事实上，由递推公式，可以得到的取值，之后可算得、直到一切的取值.

参考文献：

[1] 曹汝成.组合数学[M].广州：华南理工大学出版社，2012，1-15.

[2] 髙建福.无穷级数与连分数[M].合肥：中国科学技术出版社，2005，6-12.