組合せ数学（くみあわせすうがく、combinatorics）や組合せ論（くみあわせろん）とは、特定の条件を満たす（普通は有限の）対象からなる集まりを研究する数学の分野。特に問題とされることとして、集まりに入っている対象を数えたり（数え上げ的組合せ論）、いつ条件が満たされるのかを判定し、その条件を満たしている対象を構成したり解析したり（組合せデザインやマトロイド理論）、「最大」「最小」「最適」な対象をみつけたり（極値組合せ論や組合せ最適化）、それらの対象が持ちうる代数的構造をみつけたり（代数的組合せ論）することが挙げられる。組合せ数学は理論構築（もちろん強力な理論的手法が発展しているが）と同じくらい、（特に20世紀後半以降は）与えられた問題を解決することが目標とされる。組合せ数学のうちで最も古く取っ付きやすい部分はグラフ理論であり、今では他の様々な分野と結びつけられている。組合せ論的な問いの例として、52枚のトランプカードの並べ方は何通りあるか？というものが挙げられる。これに対する答えは 52! （52 の階乗）であり、この数は（だいたい 8.065817517094 × 10）、8 の後ろにゼロが67個もついている驚くべきスケールの大きさだとも言える。これは例えば無量大数（10）に匹敵するほど大きい。別の種類の問題には、"n"人の人でいくつかのグループを作るとき、それぞれの人が少なくとも1つのグループに属し、どの2人をとっても共通してちょうど1つのグループに属しており、どの2グループをとっても共通の人がちょうど1人ずついて、n-1人以上からなるグループがないような分け方はあるか？というものがある。答えはnにより、今でも部分的な回答しかえられていない。組み合わせ論的な記述の最も古い記録はインドに見いだすことができる。紀元前6世紀にスシュルタ()によって書かれた医学書スシュルタ・サミタ()には六つの味を63通りに組み合わせることができると書かれている。苦味、酸味、塩味、甘味、渋味、辛味を一つだけ使うか二つ一緒に使うか、三つ同時に使うか、などなど。ここで、単純な味は6種類あり、二つの組み合わせは15種類あり、三つの組み合わせは20種類ある、などがいえる。紀元前300年頃にジャイナ教の数学者によって書かれた"バガバティ・スートラ"はに対応する組合せと順列の規則を含んでいる（記号C(n, r)とP(n, r)については#繰り返しを許さない組合せと#繰り返しを許さない順列節を参照のこと。）。"n" が 2, 3, 4 の場合には実際の数値が計算されていて、さらに著者はより大きい "n" についても同じ方法で計算できると述べた。"このやり方で 5, 6, 7, ..., 10 など、あるいは数えきれるもの、数えきれないもの、無限のものまでが指定される。一時に一つのものをとる、あるいは二つのものをとる、...、十個のものをとる、組合せの数が構成された以上それらはすべて達成される。"これは算術が様々な無限大の数に拡張されうることを示唆している。組合せの数と二項展開の係数との間の関係は紀元前3世紀にピンガラ()によって楽曲の形で指摘されている。彼はグル(guru)（長音）とラグ(laghu)（短音）の様々な組み合わせをいわゆるパスカルの三角形（彼はメル・プラスターラ /「メル山（須弥山）の階段」と呼んだ）によって与え、公式に基づいてパスカルよりも単純な規則を与えている。6世紀のヴァラーハミヒラは「16 のものが 4 つの方向に行くとしたら 1820 通りの結果がある」と記している。彼はこの事実をパスカルの三角形に似た規則を用いて見いだした。9世紀にはマハーヴィーラが組合せの数を計算するアルゴリズムをはっきりとした形で与え、有名な一般式を示した。時代が下って、イスラム圏の数学者たちは遅くとも13世紀から組合せの研究をしている。13世紀の初めに北アフリカのマグレブでイブン・ムニーム(Ibn Mun'im)は組合せ論の問題に取り組んでいる。彼は "n" 種類の色をp回組み合わせる方法の場合をすべて決定する規則を述べ、帰納的にの関係の算術三角形を確立させた。彼はさらに類似の公式を、わかりやすくするためにアラビア語のアルファベットを使いながら、繰り返しを許すときや許さない順列について適用した。彼は組合せ的な理由付けについてもいくつかの仕事をしている。ペルシャの数学者アル・ファリシ()は13世紀の終わりに因数分解と組み合わせ方法に関連した考え方を導入した。アル・ファリシのアプローチは、彼自身も証明した算術の基本定理である自然数の素因数分解の一意性に基づいたものだった。アル・ファリシは三角数と二項係数の関係を見て取り、数学的帰納法の萌芽的な議論を用いて三角数や三角錐数、五胞体数、などと "n" 個の対象から "k" 個のものを選ぶ場合の数の間の関係を示している。数え上げ的組合せ論は、おきうる事象を数え上げることが17世紀のパスカルらの仕事に始まる初等的な確率論で重要な問題になってからヨーロッパで大きな関心を集めるようになった。現代的な組合せ論は19世紀の終わりに発展を始め、パーシー・アレクサンダー・マクマホンによって1915年に発表された数え上げに関する系統的な書である"組合せ解析"やロナルド・フィッシャーによる実験計画法に関する1920年代の一連の仕事などをへて、20世紀にははっきりとした研究分野として確立した。近年の主要な組合せ論学者には、主に極値組合せ論に関する仕事をしてすばらしい問題を提起し解き続けたポール・エルデシュや、1960年代における数え上げ化・代数化の定式化に大きな役割を果たしたジアン=カルロ・ロタがいる。ものをどうやって数え上げるかという研究は時に数え上げ論とよばれて別の分野だと見なされることもある。ものを順番に並べることを考えていて、一つのものが何回も選ばれてもよいとき、可能な並べかたの数はになる。ここで "n" は選ぶ候補として考えているものの数で "r" は選択の回数である。たとえば A, B, C, D の四つの文字を使って長さ三文字の文字列を作るやり方は 4 通り、つまり 64 通りある。つまり、一文字目について四つの文字のどれを選んでもよく、二文字目についてもふたたび四つの文字のどれを選んでもよく、最後の文字についてもまた四つの文字のどれを選んでもよいからである。これらをすべて掛け合わせて全体の可能性の数をえる。ものが並ぶ順番を考えていて、それぞれものは一回しか選べないときに可能な並べ方の数はになる。ここで "n" は選ぶ候補として考えているものの数で "r" は選択の回数、! 記号は階乗を表す慣用的な記号である。例えば5人の人から3人を選び出して並べる方法は 5!/(5-3)! = 60 通りある。"r" = "n" のとき（つまり選ぶ候補になっているものをすべて選ぶとき）には公式はとなる。ただし 0! = 1 と解釈することにする。例えば、3人の人がいるとき、その人たちを並べる方法は 3! つまり 3 × 2 × 1 = 6 通りある。これは、最初の人として3人のうち一人を選ぶことができ、2番目の人として残りの二人のうちどちらかを選ぶことができるが、そうすると最後に並ぶ人はもう選択の余地がないからである。これらを掛け合わせて全体の可能性の数をえる。選んだものがどの順番で並ぶかは問題でなくて、それぞれのものは一回までしか選べないときあり得る組合せの数はになる。ここで "n" は選ぶ候補の数で、"r" は選択の回数である。たとえば10個の数があってそのうちから5個を選ぶ選び方は 10!/5!(10 - 5)! = 252 通りある。選んだものがどの順番で並ぶかは問題でなくて、それぞれのものを何回でも選べるとき、あり得る組合せの数はになる。ここで "n" は選ぶ候補の数で、"r" は選択の回数である。例えば、10種類のドーナッツがあるとき3つのドーナッツを選ぶ選び方は (10 + 3 − 1)! / 3!(10 − 1)! = 220 通りある。多重集合も参照のこと。組合せ論の始まりは特定のパターンが形成される場合の数を計算することだった。"S" を "n" 個の元からなる集合とすると、"S" から "k" 個のものを選ぶ組合せは "S" の部分集合で "k" 個の元を持つもの（要素が並ぶ順番は区別されない）に対応する。"S" から "k" 個のものを選んで並べることは "k" 個の相異なる "S" の元による順列（長さが違ったり、元が同じでも順番が違う順列は区別される）に対応する。組合せや順列の数の公式は簡単に見て取れるが組合せ論のいたるところで重要な役割を果たしている。より一般的に、数え上げ組合せ論では、(通常、自然数全体の集合を添字集合とする) 有限集合の無限族 {"S"} が与えられたとき、任意の"n"に対して"S"の要素の数を数える"数え上げ関数" "f"("n")を記述する様々な方法を探究している。集合の要素数を数えるという行為はかなり大きな数学的問題であるが、組合せ的な問題では集合"S"("n")は割と単純な組合せ的記述を持ち、付加的な構造が少ししかないことが普通である。そのような関数で最も簡単なものは"閉じた公式"であり、階乗、べき乗のような単純な関数の合成で表現できるものである。例えば、上でも述べたように、"n"枚のトランプの異なる並べ方の数は"f"("n") = "n"!である．このアプローチが常に満足いくもの (すなわち実用的なもの) であるとは限らない。例えば、"f"("n")を区間[1,"n"]における異なる整数から成る部分集合で連続する2つの整数を含まないものの数であるとする。例えば、"n" = 4の場合、{}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}という集合が得られるので、"f"(4) = 8である。実際、"f"("n")が"n+2"番目のフィボナッチ数"F"("n"+2)であることが分かるので、という閉じた公式で表現できる。ここで、formula_16は黄金比である。しかしながら、ここでは数え上げ関数を見ているので、結果にformula_17が現れていることは美的に好ましくないと考えられる。"f"("n")が正整数であることを確認する他の方法として、"f"("n")がという"再帰関係"で表現できることを考えることもできる。ただし、初期条件は"f"(1) = 1と"f"(2) = 1である。他のアプローチには、"漸近公式"を見つけるというものがある。ここで、"g"("n")は「よく知られた」関数であり、"n"が無限に近づくときに"f"("n")が"g"("n")に近づくものとする。いくつかの場合では、漸近関数として複雑すぎる閉じた公式を使っても数える対象の振舞に関して何も感覚を得られないので、単純な漸近関数が好まれる。上の例では、"n"が大きいとき、となる漸近公式が導かれる。最後に、"f"("n")を"母関数"と呼ばれる形式級数で表現することもできる。母関数は大抵の場合、通常母関数であるか、あるいは指数型母関数である。母関数が一旦定まると、そこから今までに説明したアプローチで得られる全ての情報を抽出することができる。それに加えて、加算、乗算、微分などの自然な演算を母関数に施すことができることも組合せ的に意味深い。それによって、１つの組合せ的問題に対する結果を他の問題を解くために拡張することができるようになる。組合せ的パターンや組合せ的構造に関係する定理が多く存在する。これらは集合の分割や順序付分割に焦点を当てることが多い。 特に述べておきたい結果を下では紹介する。組合せ論のこの分野の単純な結果は序で述べたような集合を構成する問題に答えがあるのは"n"が"q" + "q" + 1という形をしたときのみである、というものである。しかし、"q"が素数べきのときには解が存在し、"q"が2つの平方数の和であるときは解が存在するかもしれず、そして、それ以外の正整数"q"に対して解が存在しないということを証明するのはそれ程簡単ではない。この最後の結果はBruck-Chowla-Ryserの定理と呼ばれ、有限体に基づく構成的手法と二次形式の応用を組み合わせて証明された。このような構造が存在するとき、その構造は有限射影平面と呼ばれる。有限幾何と組合せ論が交わっていることを示す例である。フランク・ラムゼイはどのような6人が集まっても、その中には常に互いに知り合いの3人か、互いに全く知らない3人が見つけられる、ということを証明した。証明は背理法による短いものである。この主張が正しくないと仮定する。これは、どの3人を見てもその中の2人は知り合いで、2人は知り合いではない、ということを意味している。ここで、この6人の中の1人を"A"としよう。残りの5人の中には"A"と知り合いである3人か、知り合いでない3人が存在する。これは、片方の否定がもう片方になることから明らかである。では、始めの方の条件をまず仮定する。このとき3人中2人以上は互いに知り合いである。なぜなら、そうでないとすると、互いに知り合いでない3人がいることになり仮定に反するからである。しかし、そうすると、その2人はAも知っているので、この3人が互いに知り合いになってしまう。これは最初の仮定に矛盾する。もう一方の条件 (残りの5人には"A"と知り合いでない3人が存在すること) を仮定する場合も同様な矛盾が導かれる。これはラムゼーの定理の特殊な場合である。無秩序な配置に秩序を見出すという考えからラムゼー理論は生まれた。一言で言うと、この理論は任意に大きな配置にはある別の種類の配置を少なくとも1つは含むことを主張している。組合せ数学のこの分野は幾何学の一部を抽象化して、線形従属関係における特定の係数に依存しないベクトル空間におけるベクトルの (普通は有限な) 集合の性質を研究している。構造的な性質だけでなく数え上げ的性質もマトロイド理論の範疇に含まれる。例えば、ユークリッド空間における"n"個のベクトルの集合が与えられたとき、それらが生成できる平面の最大数はいくつだろうか？ (答えは二項係数"C"("n

出典:wikipedia