数え上げ数学
数学における初等組合せ論 (elementary combinatorics), 有限組合せ論 (finite combinatorics), 数え上げ組合せ論 (enumerative combinatorics) あるいは数え上げの数学（かぞえあげのすうがく、英: mathematics of counting）とは、一定のパターンに従って形作られる方法の総数を扱う組合せ論の一分野を言う。この種の問題の代表例が組合せと順列の総数を算えることである。より一般には、自然数で添字付けられた有限集合 Si の無限族が与えられたとき、各 n に対する Sn に属する元の総数を数える「計数函数」(counting function) を記述することを模索するのが数え上げ数学の主題である。特定の集合に属する元の数を算えるというのはより広汎な数学的問題であるにも拘らず、そのような問題の多くは単純な組合せ論的記述に関連した応用から生じてくるのである。写像12相は順列、組合せおよび分割の数え上げに対する統一的な枠組みを与える。
最も単純な種類のパターンではそのような計数函数が、四則演算や冪あるいは階乗などの初等的な函数の合成となるような、閉じた形の式として与えられる。例えば、n 枚のカードからなる山札に対して、可能なすべての相異なる並べ方の総数は f(n) = n! で与えられる。このような閉じた式を求める問題は代数的組合せ論とも呼ばれ、しばしば漸化式や母函数を導いてそれらを適切に解くことにより所望の閉じた形へ到達する。
閉じた形の式が複雑になると、算える対象の数の増加に伴って計数函数がどのように振る舞うかが洞察しづらくなることがよく起きる。そのような場合においては、単純な漸近的近似が有効となりうる。ここで函数 g(n) が f(n) の漸近近似である: f(n) ∼ g(n) とは、f(n)/g(n) → 1 (n → ∞) が成り立つことを言う。
関連項目[編集]
参考文献[編集]
- 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.
- Joseph, George Gheverghese (1994) [1991]. The Crest of the Peacock: Non-European Roots of Mathematics (2nd ed.). London: Penguin Books. ISBN 0-14-012529-9
- 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).
- Wilf, Herbert S. (1994). Generatingfunctionology (2nd ed.). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001