f(n)を区間[1,n]における異なる整数から成る部分集合で連続する2つの整数を含まないものの数であるとする。{5}}}}という閉じた公式で表現できる。現れていることは美的に好ましくないと考えられる。f(n)=f(n-1)+f(n-2)\,\!}という再帰関係で表現できることを考えることもできる。g(n)\,}を見つけるというものがある。nが無限に近づくときにf(n)がg(n)に近づくものとする。いくつかの場合では、漸近関数として複雑すぎる閉じた公式を使っても数える対象の振舞に関して何も感覚を得られないので、単純な漸近関数が好まれる。{5}}}}となる漸近公式が導かれる。最後に、f(n)を母関数と呼ばれる形式級数で表現することもできる。{x^{n}}{n!}}}である。母関数が一旦定まると、そこから今までに説明したアプローチで得られる全ての情報を抽出することができる。自然な演算を母関数に施すことができることも組合せ的に意味深い。それによって、1つの組合せ的問題に対する結果を他の問題を解くために拡張することができるようになる。構造的組合せ論[編集]組合せ的パターンや組合せ的構造に関係する定理が多く存在する。これらは集合の分割や順序付分割に焦点を当てることが多い。述べておきたい結果を下では紹介する。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人が互いに知り合いになってしまう。これは最初の仮定に矛盾する。仮定する場合も同様な矛盾が導かれる。これはラムゼーの定理の特殊な場合である。無秩序な配置に秩序を見出すという考えからラムゼー理論は生まれた。一言で言うと、この理論は任意に大きな配置にはある別の種類の配置を少なくとも1つは含むことを主張している。集合の性質を研究している。構造的な性質だけでなく数え上げ的性質もマトロイド理論の範疇に含まれる。(答えは二項係数C(n,2)である。これらは幾何学における極値的な問題である。極値組合せ論[編集]多くの極値的な問題では集合族を扱う。次はその簡単な例である。答えは、部分集合全体の数の半分であり、すなわち、2n-1である。証明:Sを要素数nの集合とする。Tの中で高々1つしか選ぶことができない。これによって、選ぶ部分集合の最大数が部分集合の総数の半分以下になることが証明された。実際にこの数を達成できることを示すためには、Sの1要素xを持ってきて、xを含む全ての部分集合を選べばよい。難しい問題は、極値解を特徴付けることである。この場合は、要求を満たしたまま他の選び方をすると最大数が達成できないことを示すことになる。極値f(n)を見つけることでさえ難しい場合もよくあり、そのときには漸近的な評価を与えることになる。確率との関係[編集]組合せ数学を確率の基礎として応用することがある。組合せの数がわかり、それぞれの個別の事象が独立であれば、確率は組合せの数で割れば求めることができるからである[1][2]。2019年2月28日閲覧。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。Cookieに関する声明モバイルビュ。