コトバンクはYahoo!辞書と技術提携しています。

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

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

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

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

出典|ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について | 情報

組合せ論の関連キーワードオイラー(Leonhard Euler)グレコ=ラテン方陣コーニッヒの定理パスカルの三角形P対NP問題組合せ理論組合せ回路ボンビエリマルグリス真理値表デコーダ離散数学ASIC加算器タオ

今日のキーワード

優曇華

《〈梵〉udumbaraの音写「優曇波羅」の略。霊瑞、希有と訳す》1㋐インドの想像上の植物。三千年に一度その花の咲くときは転輪聖王が出現するという。㋑きわめてまれなことのたとえ。2 クサカゲロウ類が産...

続きを読む

コトバンク for iPhone

コトバンク for Android