含對(duì)角線的n階棋盤計(jì)數(shù)問題分析

【摘要】提出了含對(duì)角線n階棋盤的計(jì)數(shù)問題，利用問題解的性質(zhì)，采用兩種思路求解，將問題等價(jià)轉(zhuǎn)化為求某一函數(shù)的Taylor展開式中第n+1項(xiàng)的系數(shù)．

【關(guān)鍵詞】計(jì)數(shù)原理；冪級(jí)數(shù)；Taylor展開；級(jí)數(shù)運(yùn)算

1 問題敘述

如圖1所示，考慮一加對(duì)角線的棋盤，對(duì)角線上的點(diǎn)依次為，從到每步只能向右、向上走單位長(zhǎng)度，或在時(shí)沿走到，并稱滿足這種條件的路徑為可行路徑.易知每條可行路徑最多走步，若兩條可行路徑的步數(shù)不同或者在某一步走法不同，則說它們是不同的可行路徑.如圖所示的三條路徑均是可行路徑.

2 預(yù)備知識(shí)與符號(hào)約定

引理1 上文所述棋盤中，從到不經(jīng)過任一線段的可行路徑有種.

引理2 時(shí)，上文所述棋盤中，從到不經(jīng)過點(diǎn)集的可行路徑有種.

這里不對(duì)上述兩條引理加以證明，讀者可參考文獻(xiàn)[1].

定義1 記加對(duì)角線的n階棋盤的所有可行路徑數(shù)為.約定.并記

定義2 時(shí)，記不經(jīng)過點(diǎn)集的可行路徑為，由引理2知.約定.

3 問題求解

定理1 .

證明：給定一條可行路徑，它或者不經(jīng)過對(duì)角線，或者經(jīng)過至少某條線段.若它不經(jīng)過對(duì)角線，此時(shí)由引理1知有種走法；若經(jīng)過，設(shè)第一次經(jīng)過的線段為，則該路徑不經(jīng)過，由引理1知從到有，而從到有種走法，故由乘法原理知有種走法.再由加法原理知總共有種走法.證畢.

定理2 .

證明：由定義2知

再由定理1有，.

定理3 .

證明：由Taylor展開有

令即得結(jié)論.

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

定理4 .

下面將給出另一種求表達(dá)式的思路.

定理5 ，其中，即.

證明：給定一條可行路徑：若路徑不經(jīng)過點(diǎn)集，則有種走法；若路徑經(jīng)過中至少一點(diǎn)且第一次經(jīng)過的點(diǎn)為，則從到有種走法，從到有種走法；若路徑經(jīng)過中至少一點(diǎn)且第一次經(jīng)過的點(diǎn)為，則從到有種走法，到有種走法；由加法原理和乘法原理得.證畢.

定理6 ，其中.

證明：，由定理5知

，證畢.

定理7 .

證明：由Taylor展開可知，令即得證.

由定理6可知，由定理7代入可得，結(jié)論與定理4一致.

下面我們求的冪級(jí)數(shù)展開，進(jìn)而其冪級(jí)數(shù)展開的的系數(shù)即為所求問題的解.求解如下：

，記，注意到，，故，記，則，而，故

，

考慮上式右端的系數(shù)即得

定理8 ，其中，，.

定理8已給出的求解公式，但一項(xiàng)計(jì)算量依舊較大，可以進(jìn)一步研究求解的顯式表示，有興趣的讀者可以加以探究.下面給出時(shí)的值：

123456789

3114317370729171211150503211263

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

0123456789

01111111111

13456789101112

211162229374656677992

3436594131177233300379471577

417380811081487195825353233406850576218

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

參考文獻(xiàn)：

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

[2] 髙建福.無窮級(jí)數(shù)與連分?jǐn)?shù)[M].合肥：中國科學(xué)技術(shù)出版社，2005，6-12.