含對角線的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已給出的求解公式，但一項計算量依舊較大，可以進一步研究求解的顯式表示，有興趣的讀者可以加以探究.下面給出時的值：

123456789

3114317370729171211150503211263

例1 如圖2所示為一個的棋盤，是由一個的棋盤與一個加對角線的棋盤拼接而成，其相交部分為線段，線段由下至上依次為點.記從到的所有可行路徑數為，對于給定的一條可行路徑，其必經過某個.假設最小的值為，則該路徑必是從的左邊到達（若是從到達則與假設矛盾），依引理1知從到有種走法，從到有種走法，由計數原理知.約定，.下表給出部分的取值：

0123456789

01111111111

13456789101112

211162229374656677992

3436594131177233300379471577

417380811081487195825353233406850576218

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

參考文獻：

[1] 曹汝成.組合數學[M].廣州：華南理工大學出版社，2012，1-15.

[2] 髙建福.無窮級數與連分數[M].合肥：中國科學技術出版社，2005，6-12.