組合せ論（読み）くみあわせろん（英語表記）combinatorial analysis

ブリタニカ国際大百科事典 小項目事典

組合せ論
くみあわせろん
combinatorial analysis

配置や計画に際して起る諸問題，たとえば，それが可能であるか，もし可能なら何通りあるかなどに関して，数学的に解決を与えようとする研究分野である。古典的な理論としては，順列と組合せなどの場合の数があり，選出定理，計画の理論，最大最小の選択などの諸方面の研究がある。一般に，n 個の対象から r 個とって1列に並べる並べ方 _nP_r は，_nP_r＝n(n－1)(n－2)…(n－r＋1) で計算される。ここで n≧r である。これを n 個の対象から r 個とった順列という。また，n≧r のとき，n 個の相異なる対象から r 個を，順序を考えに入れずにとってできる組合せ (部分集合) の数 _nC_r は，_nP_r＝r!_nC_r になるから _nC_r＝n(n－1)(n－2)…(n－r＋1)/1・2・3・…・r＝n!/r!(n－r)! で表わされる。ここで 0!＝1 と定める。選出定理の基礎的なものの一つとして，P.ホールの定理がある。 N 個の元を含む集合から n 個ずつの元を含む部分集合 S₁，S₂，…，S_n をつくる。ここで異なる番号のついた部分集合 S_i，S_j が同一の対象を含んでもよいとする。このとき，各 S_n から異なる代表元 a₁∈S₁，a₂∈S₂，…，a_n∈S_n を選び出すことができるのは，すなわち i≠j ならば a_i≠a_j とできるのは，k＝1，2，…，n に対し，S₁，S₂，…，S_n のなかのどの k 個の集合も，全体として異なる対象を，少くとも k 個含んでいるときである。これは N の元を男，S_i を i が好きな女の人の集合と解釈して，結婚定理という愛称がある。計画の理論のなかで基本的なものに「ラテン方陣」や「グレコラテン方陣」がある。他のものとしては，ブロック計画がよく知られている。これは，v 個の異なる対象を b 個のブロックへ配置することであって，各ブロックがちょうど k 個の対象を含み，各対象がちょうど r 個のブロックに属し，また異なる2つの対象がちょうど λ 個のブロックに同時に属するように，計画する問題である。最大最小の選択に関する問題には，多項式時間の算法が知られている「割当ての問題」や，NP完全であることがわかっている「巡回セールスの問題」など多数の段階があり，近年では計算量の理論と関連して研究されている。

出典　ブリタニカ国際大百科事典 小項目事典