【摘 要】格路計數(shù)是組合數(shù)學(xué)中經(jīng)典的研究內(nèi)容之一，如今較為熱門的格路徑有路，路，路等。本文主要研究一種特殊的格路徑路（路的水平步用紅、藍兩色染色）。本文通過生成函數(shù)法和映射法求得n長的的個數(shù)（為數(shù)）。

【關(guān)鍵詞】路路映射法生成函數(shù)法路個數(shù)的兩種求法

一、路徑

路：路的水平步用紅、藍兩色染色的路徑，從到的路的個數(shù)為，本文主要解決為何值的問題。

二、生成函數(shù)法求

1.路的生成函數(shù)：設(shè)，接下來求 關(guān)于的函數(shù)。

設(shè)，設(shè)是上第一次回到軸上的點，現(xiàn)將分為兩段路，一段為，另一段為。由于第一段路中的第一步一定是U步，最后一步一定是D步，。所以第一段路的個數(shù)為，第二段路個數(shù)為，遍歷所有的，可得， ，所以。

2.求路的生成函數(shù)：

設(shè)，求關(guān)于的函數(shù)。設(shè)，若為H步，則；若 為U步，則

所以=，所以

所以

三、映射法求

只要找到一個和之間的一個雙射，就可以證明長為n的路的集合和長為的路的集合一一對應(yīng)，即

記：：表示所有長為的路的集合

：表示所有長為的路的集合，：表示具有個U步和個藍色H步的長為n的路的集合， U步為上步D步為下步；H步為水平步， BH藍色的水平步，RH為紅色的水平步。設(shè)，，現(xiàn)做映射如下：

第一步：若，則令，第二步：若則令，第三步：經(jīng)過一、二格路會低于零點水平位置一個單位，在所得格路前加一個U步，最后加一個D步，由以上過程，易知 為單射。

現(xiàn)驗證為滿射，我們給出的如下：

第一步：首先保持的第一步和最后一步不變。

第二步：從的第二步自左向右逐個檢查其步類型，把連續(xù)兩個U（或D）步替換成一個U（或D）步，同時將兩個構(gòu)成峰UD（或DU）的步替換成一個BH（或RH）步直至檢查完步為止，這樣我們就得到了一條格路，它的右端點在水平位置1處。

第三步：把P的最后一步接到格路的右端點上，得到一條長為的路。

第四步：從上刪除第一步和最后一步得到一條長為n的路，記為，由以上過程易知，經(jīng)過映射的作用，即可推出為滿射。

綜上所述，即為雙射，由長為和長為n的路一一對應(yīng)可得：

。

參考文獻

[1]孫毅.源自賦權(quán) 路的組合恒等式及其應(yīng)用[J].山東大學(xué)學(xué)報.2012.6.

[2]孫淑玲.組合數(shù)學(xué)引論[M].中國科學(xué)技術(shù)大學(xué)出版社.2010.4.

作者簡介：

張嘉煒（1996.01-），男，浙江慈溪人，研究方向為數(shù)學(xué)與應(yīng)用數(shù)學(xué)。