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