数え上げ数学

数学における数え上げ数学（かぞえあげすうがく、）, 初等組合せ論 (しょとうくみあわせろん、), 有限組合せ論 (ゆうげんくみあわせろん、)あるいは数え上げ組合せ論 (かぞえあげくみあわせろん、) とは、一定のパターンに従って形作られる方法の総数について研究する、組合せ論の一分野である。

この種の問題の代表例が組合せと順列の総数を算えることである。より一般には、自然数で添字付けられた有限集合  の無限族が与えられたとき、各  に対する  に属する元の総数を数える「計数函数（）」の記述を模索することが、この数え上げ数学の主題である。特定の集合に属する元の数を算えるというのはより広汎なであるにも拘らず、そのような問題の多くは単純な組合せ論的記述に関連した応用から生じてくるのである。写像12相は順列、組合せおよび分割の数え上げに対する統一的な枠組みを与える。

最も単純な種類のパターンではそのような計数函数が、四則演算や冪あるいは階乗などの初等的な函数の合成となるような、として与えられる。例えば、 枚のカードからなる山札に対して、可能なすべての相異なる並べ方の総数は  で与えられる。このような閉じた式を求める問題はとも呼ばれ、しばしば漸化式や母函数を導いてそれらを適切に解くことにより所望の閉じた形へ到達する。

閉じた形の式が複雑になると、算える対象の数の増加に伴って計数函数がどのように振る舞うかが洞察しづらくなることがよく起きる。そのような場合においては、単純な近似が有効となりうる。ここで函数  が  の漸近近似である:  とは、 が成り立つことをいう。

 関連項目 
 順列
 場合の数
 数え上げ
 組合せ (数学)
 組合せ数学
 置換 (数学)
 重複置換
 写像12相
 樹形図
 離散数学
 グラフ理論
 数論



 組合せ爆発
 包除原理



 ポーヤの計数定理
 バーンサイドの補題

 参考文献 
 Zeilberger, D., Enumerative and Algebraic Combinatorics
 Bjorner, A. and Stanley, R. P., A Combinatorial Miscellany
 Graham, R.L.,  Grötschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2.  Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.

 Loehr, Nicholas A. (2011).  Bijective Combinatorics.  CRC Press.  ISBN  143984884X,  ISBN  978-1439848845.
 Stanley, Richard P. (1997, 1999).  Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press.  ISBN 0-521-55309-1, ISBN 0-521-56069-1.
 Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
 Riordan, John (1958). An Introduction to Combinatorial Analysis, Wiley & Sons, New York (republished). 
 Riordan, John (1968). Combinatorial identities, Wiley & Sons, New York (republished).


Category:組合せ論
Category:数学に関する記事