数え上げ数学
数学における初等組合せ論 (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. http://www.math.upenn.edu/%7Ewilf/DownldGF.html