組合くみあわせ数学すうがく

組合くみあわせ数学すうがく（くみあわせすうがく、英語えいご: combinatorics）あるいは組合くみあわせ論ろん（くみあわせろん）とは、特定とくていの条件じょうけんを満みたす（普通ふつうは有限ゆうげんの）対象たいしょうからなる集あつまりを研究けんきゅうする数学すうがくの分野ぶんや。離散りさん数学すうがくの中核ちゅうかくの一ひとつとされる。特とくに問題もんだいとされることとして、

• 集合しゅうごうに入はいっている対象たいしょうを数かぞえたり（数かぞえ上あげ組合くみあわせ論ろん）、
• いつ条件じょうけんが満みたされるのかを判定はんていし、その条件じょうけんを満みたしている対象たいしょうを構成こうせいしたり解析かいせきしたり（組合くみあわせデザイン）、
• 「最大さいだい」「最小さいしょう」の対象たいしょうを求もとめたり（極きょく値ち組合くみあわせ論ろん）、
• 対象たいしょうが持もつ代数だいすう的てき構造こうぞうを明あきらかにしたり（代数だいすう的てき組合くみあわせ論ろん）

することが挙あげられる。要素ようそ同士どうしの繋つながりを扱あつかうグラフ理論りろんも組合くみあわせ論ろんの一いち分野ぶんやとされ、MSC2020においては、大分おおいた類るいとして組合くみあわせ論ろんに05が、中ちゅう分類ぶんるいとして数かぞえ上あげ組合くみあわせ論ろんに05A、デザインと配置はいちに05B、グラフ理論りろんに05C、極きょく値ち組合くみあわせ論ろんに05D、代数だいすう的てき組合くみあわせ論ろんに05Eが割わり当あてられている。

概観がいかんと歴史れきし

組合くみあわせ数学すうがくは理論りろん構築こうちくと同おなじくらい、（特とくに20世紀せいき後半こうはん以降いこうは）与あたえられた問題もんだいを解決かいけつすることが目標もくひょうになっている。組合くみあわせ数学すうがくのうちで最もっとも古ふるく取とっ付つきやすいものはグラフ理論りろんであり、今いまでは他たの様々さまざまな分野ぶんやと結むすびつけられている。

組合くみあわせ論ろん的てきな問といの例れいとして、52枚まいのトランプカードの並ならべ方かたは何なん通とおりあるか？というものが挙あげられる。これに対たいする答こたえは 52! （52 の階かい乗じょう）であり、この数かずは（だいたい 8.065817517094 × 10⁶⁷）、8 の後うしろにゼロが67個こもついている驚おどろくべきスケールの大おおきさだとも言いえる。これは例たとえば無量むりょう大数たいすう（10⁶⁸）に匹敵ひってきするほど大おおきい。

別べつの種類しゅるいの問題もんだいには、n人ひとの人ひとでいくつかのグループを作つくるとき、それぞれの人ひとが少すくなくとも1つのグループに属ぞくし、どの2人ふたりをとっても共通きょうつうしてちょうど1つのグループに属ぞくしており、どの2グループをとっても共通きょうつうの人ひとがちょうど1人にんずついて、n-1人ひとり以上いじょうからなるグループがないような分わけ方かたはあるか？というものがある。答こたえはnにより、今いまでも部分ぶぶん的てきな回答かいとうしかえられていない。 組くみ合あわせ論ろん的てきな記述きじゅつの最もっとも古ふるい記録きろくはインドに見みいだすことができる。紀元前きげんぜん6世紀せいきにスシュルタ(en:Sushruta)によって書かかれた医学いがく書しょスシュルタ・サミタ(en:Sushruta Samhita)には六むっつの味あじを63通とおりに組くみ合あわせることができると書かかれている。苦味にがみ、酸味さんみ、塩味しおあじ、甘味あまみ、渋しぶ味あじ、辛味からみを一ひとつだけ使つかうか二ふたつ一緒いっしょに使つかうか、三みっつ同時どうじに使つかうか、などなど。ここで、単純たんじゅんな味あじは6種類しゅるいあり、二ふたつの組くみ合あわせは15種類しゅるいあり、三みっつの組くみ合あわせは20種類しゅるいある、などがいえる。紀元前きげんぜん300年ねん頃ころにジャイナ教きょうの数学すうがく者しゃによって書かかれたバガバティ・スートラは

$\ C(n,1)=n$, $C(n,2)={\frac {n(n-1)}{1\cdot 2}}$, $C(n,3)={\frac {n(n-1)(n-2)}{1\cdot 2\cdot 3}}$

$\ P(n,1)=n$, $\ P(n,2)=n(n-1)$, $\ P(n,3)=n(n-1)(n-2)$

に対応たいおうする組合くみあわせと順列じゅんれつの規則きそくを含ふくんでいる（記号きごうC(n, r)とP(n, r)については#繰くり返かえしを許ゆるさない組合くみあわせと#繰くり返かえしを許ゆるさない順列じゅんれつ節ふしを参照さんしょうのこと。）。

n が 2, 3, 4 の場合ばあいには実際じっさいの数値すうちが計算けいさんされていて、さらに著者ちょしゃはより大おおきい n についても同おなじ方法ほうほうで計算けいさんできると述のべた。

このやり方かたで 5, 6, 7, ..., 10 など、あるいは数かぞえきれるもの、数かぞえきれないもの、無限むげんのものまでが指定していされる。一時いちじに一ひとつのものをとる、あるいは二ふたつのものをとる、...、十じゅう個このものをとる、組合くみあわせの数かずが構成こうせいされた以上いじょうそれらはすべて達成たっせいされる。

これは算術さんじゅつが様々さまざまな無限むげん大だいの数かずに拡張かくちょうされうることを示唆しさしている。組合くみあわせの数かずと二に項こう展開てんかいの係数けいすうとの間あいだの関係かんけいは紀元前きげんぜん3世紀せいきにピンガラ(en:Pingala)によって楽曲がっきょくの形かたちで指摘してきされている。彼かれはグル(guru)（長音ちょうおん）とラグ(laghu)（短音たんおん）の様々さまざまな組くみ合あわせをいわゆるパスカルの三角形さんかっけい（彼かれはメル・プラスターラ /「メル山さん（須弥山しゅみせん）の階段かいだん」と呼よんだ）によって与あたえ、公式こうしき

$\ C(n+1,r)=C(n,r)+C(n,r-1)$

に基もとづいてパスカルよりも単純たんじゅんな規則きそくを与あたえている。

6世紀せいきのヴァラーハミヒラは「16 のものが 4 つの方向ほうこうに行いくとしたら 1820 通とおりの結果けっかがある」と記しるしている。彼かれはこの事実じじつをパスカルの三角形さんかっけいに似にた規則きそくを用もちいて見みいだした。9世紀せいきにはマハーヴィーラが組合くみあわせの数かずを計算けいさんするアルゴリズムをはっきりとした形かたちで与あたえ、有名ゆうめいな一般いっぱん式しき

$C(n,r)={\frac {n(n-1)(n-2)\cdots (n-r+1)}{r!}}$

を示しめした。

時代じだいが下くだって、イスラム圏けんの数学すうがく者しゃたちは遅おそくとも13世紀せいきから組合くみあわせの研究けんきゅうをしている。13世紀せいきの初はじめに北きたアフリカのマグレブでイブン・ムニーム(Ibn Mun'im)は組合くみあわせ論ろんの問題もんだいに取とり組くんでいる。彼かれは n 種類しゅるいの色いろをp回かい組くみ合あわせる方法ほうほうの場合ばあいをすべて決定けっていする規則きそくを述のべ、帰納的きのうてきに

$\ C(n,p)=C(n-1,p-1)+C(n-2,p-1)+\dots +C(p-1,p-1)$

の関係かんけいの算術さんじゅつ三角形さんかっけいを確立かくりつさせた。彼かれはさらに類似るいじの公式こうしきを、わかりやすくするためにアラビア語ごのアルファベットを使つかいながら、繰くり返かえしを許ゆるすときや許ゆるさない順列じゅんれつについて適用てきようした。彼かれは組合くみあわせ的てきな理由りゆう付づけについてもいくつかの仕事しごとをしている。

ペルシャの数学すうがく者しゃアル・ファリシ(en:Al-Farisi)は13世紀せいきの終おわりに因数いんすう分解ぶんかいと組くみ合あわせ方法ほうほうに関連かんれんした考かんがえ方かたを導入どうにゅうした。アル・ファリシのアプローチは、彼かれ自身じしんも証明しょうめいした算術さんじゅつの基本きほん定理ていりである自然しぜん数すうの素因数そいんすう分解ぶんかいの一意いちい性せいに基もとづいたものだった。アル・ファリシは三角さんかく数すうと二に項こう係数けいすうの関係かんけいを見みて取とり、数学すうがく的てき帰納きのう法ほうの萌芽ほうが的てきな議論ぎろんを用もちいて三角さんかく数すうや三さん角錐かくすい数すう、五ご胞体数すう、などと n 個この対象たいしょうから k 個このものを選えらぶ場合ばあいの数かずの間あいだの関係かんけいを示しめしている。

数かぞえ上あげ的てき組合くみあわせ論ろんは、おきうる事象じしょうを数かぞえ上あげることが17世紀せいきのパスカルらの仕事しごとに始はじまる初等しょとう的てきな確率かくりつ論ろんで重要じゅうような問題もんだいになってからヨーロッパで大おおきな関心かんしんを集あつめるようになった。現代げんだい的てきな組合くみあわせ論ろんは19世紀せいきの終おわりに発展はってんを始はじめ、パーシー・アレクサンダー・マクマホンによって1915年ねんに発表はっぴょうされた数かぞえ上あげに関かんする系統的けいとうてきな書しょである組合くみあわせ解析かいせきやロナルド・フィッシャーによる実験じっけん計画けいかく法ほうに関かんする1920年代ねんだいの一連いちれんの仕事しごとなどをへて、20世紀せいきにははっきりとした研究けんきゅう分野ぶんやとして確立かくりつした。近年きんねんの主要しゅような組合くみあわせ論ろん学者がくしゃには、主おもに極きょく値ち組合くみあわせ論ろんに関かんする仕事しごとをしてすばらしい問題もんだいを提起ていきし解とき続つづけたポール・エルデシュや、1960年代ねんだいにおける数かぞえ上あげ化か・代数だいすう化かの定式ていしき化かに大おおきな役割やくわりを果はたした ジャン・カルロ・ロタがいる。ものをどうやって数かぞえ上あげるかという研究けんきゅうは時ときに数かぞえ上あげ論ろんとよばれて別べつの分野ぶんやだと見みなされることもある。

順列じゅんれつと組合くみあわせ

繰くり返かえしを許ゆるした順列じゅんれつ

ものを順番じゅんばんに並ならべることを考かんがえていて、一ひとつのものが何なん回かいも選えらばれてもよいとき、可能かのうな並ならべかたの数かずは

$n^{r}$

になる。ここで n は選えらぶ候補こうほとして考かんがえているものの数かずで r は選択せんたくの回数かいすうである。

たとえば A, B, C, D の四よっつの文字もじを使つかって長ながさ三さん文字もじの文字もじ列れつを作つくるやり方かたは 4³ 通とおり、つまり 64 通とおりある。つまり、一文字ひともじ目めについて四よっつの文字もじのどれを選えらんでもよく、二に文字もじ目めについてもふたたび四よっつの文字もじのどれを選えらんでもよく、最後さいごの文字もじについてもまた四よっつの文字もじのどれを選えらんでもよいからである。これらをすべて掛かけ合あわせて全体ぜんたいの可能かのう性せいの数かずをえる。

繰くり返かえしを許ゆるさない順列じゅんれつ

ものが並ならぶ順番じゅんばんを考かんがえていて、それぞれものは一いち回かいしか選えらべないときに可能かのうな並ならべ方かたの数かずは

$P(n,r)={\frac {n!}{(n-r)!}}=n_{(r)}$

になる。ここで n は選えらぶ候補こうほとして考かんがえているものの数かずで r は選択せんたくの回数かいすう、! 記号きごうは階かい乗じょうを表あらわす慣用かんよう的てきな記号きごう、$n_{(r)}$は降くだ冪べきを意味いみするポッホハマー記号きごうである。

例たとえば5人にんの人ひとから3人にんを選えらび出だして並ならべる方法ほうほうは 5!/(5-3)! = 60 通とおりある。

r = n のとき（つまり選えらぶ候補こうほになっているものをすべて選えらぶとき）には公式こうしきは

${\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$

となる。ただし 0! = 1 と解釈かいしゃくすることにする。

例たとえば、3人にんの人ひとがいるとき、その人ひとたちを並ならべる方法ほうほうは 3! つまり 3 × 2 × 1 = 6 通とおりある。これは、最初さいしょの人ひととして3人にんのうち一いち人にんを選えらぶことができ、2番目ばんめの人ひととして残のこりの二人ふたりのうちどちらかを選えらぶことができるが、そうすると最後さいごに並ならぶ人ひとはもう選択せんたくの余地よちがないからである。これらを掛かけ合あわせて全体ぜんたいの可能かのう性せいの数かずをえる。

繰くり返かえしを許ゆるさない組合くみあわせ

選えらんだものがどの順番じゅんばんで並ならぶかは問題もんだいでなくて、それぞれのものは一いち回かいまでしか選えらべないときあり得える組合くみあわせの数かずは

$C(n,r)={{n!} \over {r!(n-r)!}}={n \choose r}$

になる。ここで n は選えらぶ候補こうほの数かずで、r は選択せんたくの回数かいすうである。

たとえば10個この数かずがあってそのうちから5個こを選えらぶ選えらび方かたは ${{10!} \over {5!(10-5)!}}=252$ 通とおりある。

繰くり返かえしを許ゆるした組合くみあわせ

選えらんだものがどの順番じゅんばんで並ならぶかは問題もんだいでなくて、それぞれのものを何なん回かいでも選えらべるとき、あり得える組合くみあわせの数かずは

${{(n+r-1)!} \over {r!(n-1)!}}={{n+r-1} \choose {r}}={{n+r-1} \choose {n-1}}$

になる。ここで n は選えらぶ候補こうほの数かずで、r は選択せんたくの回数かいすうである。

例たとえば、10種類しゅるいのドーナッツがあるとき3つのドーナッツを選えらぶ選えらび方かたは ${{(10+3-1)!} \over {3!(10-1)!}}=220$ 通とおりある。多重たじゅう集合しゅうごうも参照さんしょうのこと。

数かぞえ上あげ組合くみあわせ論ろん

組合くみあわせ論ろんの始はじまりは特定とくていのパターンが形成けいせいされる場合ばあいの数かずを計算けいさんすることだった。S を n 個この元もとからなる集合しゅうごうとすると、S から k 個このものを選えらぶ組合くみあわせは S の部分ぶぶん集合しゅうごうで k 個この元もとを持もつもの（要素ようそが並ならぶ順番じゅんばんは区別くべつされない）に対応たいおうする。S から k 個このものを選えらんで並ならべることは k 個この相そう異ことなる S の元もとによる順列じゅんれつ（長ながさが違ちがったり、元もとが同おなじでも順番じゅんばんが違ちがう順列じゅんれつは区別くべつされる）に対応たいおうする。組合くみあわせや順列じゅんれつの数かずの公式こうしきは簡単かんたんに見みて取とれるが組合くみあわせ論ろんのいたるところで重要じゅうような役割やくわりを果はたしている。

より一般いっぱん的てきに、数かぞえ上あげ組合くみあわせ論ろんでは、(通常つうじょう、自然しぜん数すう全体ぜんたいの集合しゅうごうを添字そえじ集合しゅうごうとする) 有限ゆうげん集合しゅうごうの無限むげん族ぞく {S_i} が与あたえられたとき、任意にんいのnに対たいしてS_nの要素ようその数かずを数かぞえる数かぞえ上あげ関数かんすう 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)であることが分わかるので、

$f(n)={\frac {\phi ^{n+2}-(1-\phi )^{n+2}}{\sqrt {5}}}$

という閉とじた公式こうしきで表現ひょうげんできる。ここで、$\phi =(1+{\sqrt {5}})/2$は黄金おうごん比ひである。しかしながら、ここでは数かぞえ上あげ関数かんすうを見みているので、結果けっかに${\sqrt {5}}$が現あらわれていることは美的びてきに好このましくないと考かんがえられる。f(n)が正せい整数せいすうであることを確認かくにんする他ほかの方法ほうほうとして、f(n)が

$f(n)=f(n-1)+f(n-2)\,\!$

という再帰さいき関係かんけいで表現ひょうげんできることを考かんがえることもできる。 ただし、初期しょき条件じょうけんはf(1) = 1とf(2) = 1である。

他たのアプローチには、漸近ぜんきん公式こうしき

$f(n)\sim g(n)\,$

を見みつけるというものがある。 ここで、g(n)は「よく知しられた」関数かんすうであり、 nが無限むげんに近ちかづくときにf(n)がg(n)に近ちかづくものとする。 いくつかの場合ばあいでは、漸近ぜんきん関数かんすうとして複雑ふくざつすぎる閉とじた公式こうしきを使つかっても数かぞえる対象たいしょうの振舞ふるまいに関かんして何なにも感覚かんかくを得えられないので、単純たんじゅんな漸近ぜんきん関数かんすうが好このまれる。上うえの例れいでは、nが大おおきいとき、

$f(n)\sim {\frac {\phi ^{n+2}}{\sqrt {5}}}$

となる漸近ぜんきん公式こうしきが導みちびかれる。

最後さいごに、f(n)を母はは関数かんすうと呼よばれる形式けいしき級数きゅうすうで表現ひょうげんすることもできる。 母はは関数かんすうは大抵たいていの場合ばあい、通常つうじょう母はは関数かんすう

$\sum _{n\geq 0}f(n)x^{n}$

であるか、あるいは指数しすう型がた母はは関数かんすう

$\sum _{n\geq 0}f(n){\frac {x^{n}}{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,2)である。) では、生成せいせいする平面へいめんの数かずがこれよりもちょうど1つだけ数かずが少すくなくなるベクトルの集合しゅうごうは存在そんざいするだろうか？ これらは幾何きか学がくにおける極きょく値ち的てきな問題もんだいである。

極きょく値ち組合くみあわせ論ろん

多おおくの極きょく値ち的てきな問題もんだいでは集合しゅうごう族ぞくを扱あつかう。次つぎはその簡単かんたんな例れいである。「要素ようそ数すうnの集合しゅうごうの部分ぶぶん集合しゅうごうの族ぞくで、どの2つも交まじわるようものの最大さいだいサイズはいくつだろうか？」 答こたえは、部分ぶぶん集合しゅうごう全体ぜんたいの数かずの半分はんぶんであり、すなわち、2^n-1である。証明しょうめい：Sを要素ようそ数すうnの集合しゅうごうとする。任意にんいの部分ぶぶん集合しゅうごうTとその補ほ集合しゅうごうS − Tの中なかで高々たかだか1つしか選えらぶことができない。これによって、選えらぶ部分ぶぶん集合しゅうごうの最大さいだい数すうが部分ぶぶん集合しゅうごうの総数そうすうの半分はんぶん以下いかになることが証明しょうめいされた。実際じっさいにこの数かずを達成たっせいできることを示しめすためには、Sの1要素ようそxを持もってきて、xを含ふくむ全すべての部分ぶぶん集合しゅうごうを選えらべばよい。

より難むずかしい問題もんだいは、極きょく値ち解かいを特徴付とくちょうづけることである。この場合ばあいは、要求ようきゅうを満みたしたまま他たの選えらび方かたをすると最大さいだい数すうが達成たっせいできないことを示しめすことになる。

極きょく値ちf(n)を見みつけることでさえ難むずかしい場合ばあいもよくあり、そのときには漸近ぜんきん的てきな評価ひょうかを与あたえることになる。

確かく率りつとの関係かんけい

組合くみあわせ数学すうがくを確かく率りつの基礎きそとして応用おうようすることがある。組合くみあわせの数かずがわかり、それぞれの個別こべつの事象じしょうが独立どくりつであれば、確かく率りつは組合くみあわせの数かずで割われれば求もとめることができるからである。

関連かんれん文献ぶんけん

• Graham, R.L., Groetschel 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-26207169-X .
• Joseph, George Gheverghese (2000). The Crest of the Peacock: Non-European Roots of Mathematics, 2nd Edition. Penguin Books. ISBN 0-14-027778-1.
• Katz, Victor J. (1998). A History of Mathematics: An Introduction, 2nd Edition. Addison-Wesley Education Publishers. ISBN 0-32101618-1.
• van Lint, J.H., and Wilson, R.M. (2001). A Course in Combinatorics, 2nd Edition. Cambridge University Press. ISBN 0-521-80340-3.
  • ヴァン・リント&ウィルソン 組合くみあわせ論ろん 上じょう 神保じんぼ雅一まさいち (監修かんしゅう, 翻訳ほんやく), 澤さわ正憲まさのり (翻訳ほんやく), 萩田はぎた真理子まりこ (翻訳ほんやく), 丸善まるぜん出版しゅっぱん, ISBN 978-4-62130-245-3, (2018).
• O'Connor, John J. and Robertson, Edmund F. (1999-2004). MacTutor History of Mathematics archive. St Andrews University.
• Rashed, R. (1994). The development of Arabic mathematics : between arithmetic and algebra. London.
• Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.
• やさしい組合くみあわせ数学すうがく 西岡にしおか弘明ひろあき, コロナ社しゃ, ISBN 978-4-339-02362-6 (1999).

関連かんれん項目こうもく

• 順列じゅんれつ
• 組合くみあわせ (数学すうがく)
• 数かぞえ上あげ数学すうがく
• 組合くみあわせ爆発ばくはつ
• 写像しゃぞう12相そう (Twelvefold way)

外部がいぶリンク

• Combinatorial Software and Databases