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