組合數(shù)學(xué)中的K-路徑問題研究.pdf

1、組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計數(shù)、分析和優(yōu)化的一門學(xué)科?，F(xiàn)代組合數(shù)學(xué)研究的主要內(nèi)容之一是集合的組合結(jié)構(gòu)，即把集合的元素按要求分成各種組態(tài)的理論和技術(shù)。對各種事件、序列、圖形等的計數(shù)和枚舉是組合分析的主要研究內(nèi)容。其中一個最基本的研究對象是排列和組合，對于排列上的各種統(tǒng)計量和性質(zhì)的研究，以及相關(guān)的多重排列、分拆、對合和匹配等結(jié)構(gòu)的研究始終是組合數(shù)學(xué)的重要課題。特別是對排列等結(jié)構(gòu)加限制，即有禁排列、有禁分拆等問題，在最近的十幾年來更是引起

2、許多組合數(shù)學(xué)家的興趣和關(guān)注，成為了組合數(shù)學(xué)中的一個新的方向和熱點。 另一個基本研究對象是格路徑和樹，它們自身的結(jié)構(gòu)、計數(shù)的研究一直是組合數(shù)學(xué)中的重要部分，而且在生物信息學(xué)、計算機(jī)科學(xué)、物理學(xué)中都有廣泛的應(yīng)用。由于格路徑和樹結(jié)構(gòu)天然的直觀性，組合數(shù)學(xué)中的許多問題都可以歸結(jié)為對格路徑和樹結(jié)構(gòu)的探討。 組合數(shù)學(xué)的主要研究方法有反演公式方法、生成函數(shù)方法，遞歸公式方法，組合雙射法等。其中生成函數(shù)方法，遞歸公式方法是基本的方法，組

3、合雙射法可以直觀而簡單地給出事件、序列和圖形之間的關(guān)系與內(nèi)在的結(jié)構(gòu)。近年來，這種構(gòu)造性的組合數(shù)學(xué)成為組合數(shù)學(xué)領(lǐng)域的一個非常熱門的課題。 本文對組合數(shù)學(xué)中的三種格路徑Dyck路徑、Motzkin路徑和、Schr(o)der路徑進(jìn)行研究，并將它們統(tǒng)一起來做以推廣，提出了k-路徑：由上升步(1，1)，下降步(1，-1)和水平步(k，0)構(gòu)成的，從(0，0)到(n，0)的格路徑。并且還給出了這幾類格路徑與有序樹之間的雙射關(guān)系。