地圖計數

地圖計數(enumeration of map)求一類組合數.具體地說,在給定可定向性和虧格之下,確定滿足各種參數限制條件的不同構的地圖的數目.這就是地圖計數問題,或簡稱地圖計數.通常,有如下三類問題:
1.單參數問題,即在頂點數、邊數或面數之一個給定的情況下,確定的不同構地圖的數目.
2.雙參數問題,即在已知頂點數、邊數或面數中之兩個給定的情形下,確定不同構地圖的數目.
3.頂點剖分問題,即當頂點的度為i>1的頂點數目,對於i=1,2,…都給出了的情形下,確定不同構地圖的數目.
一般地,這些問題都是相當困難的,而且難度隨上述的次序遞增.即使在單參數的情況,對於凸多面體(相當於3連通的平面地圖)至今仍未得到一個有效的計數公式.對於有根地圖的計數,目前主要集中在平面地圖上.對於一般的情形,也有所進展.
給定一類地圖,記}l為所有這類地圖所組成的集合,n;<i)l)表示所考慮的參數.函式
地圖計數
稱為.}l的地圖計數函式..f.} }xl } x2, "..)所滿足的方程稱為計數方程一般而言,要想求某類地圖的計數,首先要求出它的計數方程,然後通過解這個方程來確定出計數函式.最理想的結果是,所得的計數函式的係數為單項式,或稱無和式.然而這種表達式不一定存在或雖存在也不易求得.次理想的結果是正和式,即將這種係數表示為正單項式和.

相關詞條

熱門詞條

聯絡我們