数え上げ数学
 | この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
数学における数え上げ数学（かぞえあげすうがく、英: mathematics of counting）, 初等組合せ論 (しょとうくみあわせろん、英: elementary combinatorics), 有限組合せ論 (ゆうげんくみあわせろん、英: finite combinatorics)あるいは数え上げ組合せ論 (かぞえあげくみあわせろん、英: enumerative combinatorics) とは、一定のパターンに従って形作られる方法の総数について研究する、組合せ論の一分野である。
この種の問題の代表例が組合せと順列の総数を算えることである。より一般には、自然数で添字付けられた有限集合 Si の無限族が与えられたとき、各 n に対する Sn に属する元の総数を数える「計数函数（英: counting function）」の記述を模索することが、この数え上げ数学の主題である。特定の集合に属する元の数を算えるというのはより広汎な数学的問題であるにも拘らず、そのような問題の多くは単純な組合せ論的記述に関連した応用から生じてくるのである。写像12相は順列、組合せおよび分割の数え上げに対する統一的な枠組みを与える。
最も単純な種類のパターンではそのような計数函数が、四則演算や冪あるいは階乗などの初等的な函数の合成となるような、閉じた形の式として与えられる。例えば、n 枚のカードからなる山札に対して、可能なすべての相異なる並べ方の総数は f(n) = n! で与えられる。このような閉じた式を求める問題は代数的組合せ論とも呼ばれ、しばしば漸化式や母函数を導いてそれらを適切に解くことにより所望の閉じた形へ到達する。
閉じた形の式が複雑になると、算える対象の数の増加に伴って計数函数がどのように振る舞うかが洞察しづらくなることがよく起きる。そのような場合においては、単純な漸近的近似が有効となりうる。ここで函数 g(n) が f(n) の漸近近似である: f(n) ∼ g(n) とは、f(n)/g(n) → 1 (n → ∞) が成り立つことをいう。
関連項目
[編集]- 順列
- 場合の数
- 数え上げ
- 組合せ (数学)
- 組合せ数学
- 置換 (数学)
- 重複置換
- 写像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.
- 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