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

組合せ理論 くみあわせりろんcombinatorics

翻訳|combinatorics

世界大百科事典 第2版の解説

くみあわせりろん【組合せ理論 combinatorics】

物の,組合せ的性質をもつ規則による選び方や,配列のしかたの数を考察する数学の一分野。組合せ数学とも呼ばれる。ある集合からいくつかのものを選び出す方法が何通りあるかを調べる順列・組合せの問題,多くの変数がいくつかの一次不等式を満たすという条件の下で,与えられた一次不等式を最大または最小にすることを考える線形計画法一筆書きのようなグラフの組合せ的性質を調べること,オイラー方陣のような直交するラテン方陣の存在を考察するなど,これらは組合せ理論の例であり,数学のほとんど全分野に,その対象を見いだすことができる。

出典 株式会社日立ソリューションズ・クリエイト世界大百科事典 第2版について 情報

日本大百科全書(ニッポニカ)の解説

組合せ理論
くみあわせりろん

与えられた条件を満たす配置の数え上げおよびその構成の問題を取り扱う数学の分野。組合せ理論の始まりは、問題にしている場合の数、または方法の数をもれなく数え上げることであった。確率の理論の初期の発展段階におけるパスカル、フェルマー、ベルヌーイなどの学者の研究は、本質的には組合せの問題に関するものであった。次に、順列・組合せから始めて、典型例をあげる。[古屋 茂]

順列と組合せ

(1)n個の異なるものからr個取り出し1列に並べたものを、n個のものからr個とった順列という。その総数をnPrで表す。

(2)n個の異なるものからr個取り出して得られた集合を、n個のものからr個とった組合せという。その総数をnCrで表す。

(3)n個の異なるものから繰り返してとることを許してr個取り出して1列に並べたものを、n個のものからr個とった重複(じゅうふく)順列という。その総数はnrである。
(4)n個の異なるものから同じものをとってもよいことにしてr個取り出して得られた集合を、n個のものからr個とった重複組合せという。
その総数はn+r+1Crである。[古屋 茂]

n個のものを分ける方法の数

(1)n個の相異なるものをk人に分配する方法(1個も受け取らない人がいてもよいとする)の数はknである。
(2)同じ種類のn個のものをk人に分配する方法(1個も受け取らない人がいてもよいとする)の数はn+k-1Cnである。
(3)相異なるn個のものをちょうどk個の山に分ける方法の数をSnkで表すと

Snkを(第2種の)スターリング数という。
(4)同じ種類のn個のものをちょうどk個の山に分ける方法の数は、自然数nをちょうどk個の自然数の和として表す方法の数qk(n)に等しい。qk(n)をnとkの関数として簡単な形に表すことはむずかしい。
(5)相異なるn個のものをいくつかの山に分ける方法の数をBnとすると

Bnをベル数とよぶ。
(6)同じ種類のn個のものをいくつかの山に分ける方法の数は、自然数nをいくつかの自然数の和に分ける方法の数p(n)に等しい。

P(n)をnの分割数という。次に、n=1, 2,……, 10の場合について、P(n)を示しておく。
[古屋 茂]

カークマンの女生徒問題

15人の女生徒が毎日3人ずつ5組に分かれて散歩に出かける。1週間の間に15人のうちのどの2人も、ちょうど1回だけ同じ組になるようにするには、組分けをどのようにすればよいか。これがカークマンの女生徒問題である。カークマンは1847年にこの問題を提起しその解答を与えている。この問題の一つの解答をあげておく。15人の女生徒を1から15までの数で表す。
[古屋 茂]

マージャン総当りの問題

参加者が16人のマージャン会を開く。始めに4人ずつの組に分かれて4卓でゲームを行い、すべての卓で規定の勝負が終わったところで、組分けを別にして2回目の勝負に移る。これを続けて全体で5回の勝負を行うのであるが、16人のどの2人も5回のうちのちょうど1回だけ同じ卓でゲームをするようにしたい。どのような組合せをつくればよいかというのが問題である。
 次に一つの解答をあげる。16人を1から16までの数で表す。横に並んだ4人が同じ卓につくものとする。
[古屋 茂]

ラテン方格・オイラー方格

アルファベット(ラテン文字)を正方形の形に並べ、どの行どの列にも全部の文字がちょうど1個ずつあるように配列したもの(たとえば 次の図のように)をラテン方格またはラテン方陣という。
  A B C D
  B C D A
  C D A B
  D A B C
 フィッシャーは農事試験において実験を効果的に計画するためラテン方格の考えを利用した。ラテン方格において用いられている文字の個数をラテン方格の次数という。次数がnのラテン方格において、第1行および第1列が与えられた基準の順列であるものを標準形ラテン方格という。n次標準形ラテン方格がいくつあるか。その個数をL(n)で表すと

n次ラテン方格の総数はn!(n-1)!L(n)である。
 ラテン文字で書かれたラテン方格とギリシア文字で書かれたラテン方格とを重ねて、次図のように同一の対が現れないように配列したものをオイラー方格またはグレコ・ラテン方格という。
  Aα Bβ Cγ
  Bγ Cα Aβ
  Cβ Aγ Bα
 一般にn次ラテン方格を二つ重ねて正方形をなすn2個の欄にn2個の相異なる対が配置されているとき、それをn次オイラー方格という。nが奇数の場合とnが4の倍数の場合にオイラー方格をつくることは容易である。nが偶数で4の倍数でない場合にはオイラー方格は存在しないだろうとオイラーは予想した。二次オイラー方格が存在しないことは明らかである。六次オイラー方格が存在しないことはタリーG. Tarryが試行によって確かめた(1900)。1959年に至ってn≠2, n≠6のときn次オイラー方格がつくられることがボースRaj Chandra Boseや、パーカーErnest Tilden Parkerや、シュリクハンドShrikhandeによって証明された。
 カークマンの女生徒問題、マージャン総当りの問題、ラテン方格・オイラー方格はどれも、ある条件を満たすような配置を構成せよという問題である。このような型の問題に対しては有限体上の幾何学の考えが有効である。組合せ理論には多くの興味ある問題があるが、これらについては後記の文献をみられたい。[古屋 茂]
『高橋磐郎著『組合せ理論とその応用』(1979・岩波全書) ▽山本幸一著『数学入門シリーズ5 順列・組合せと確率』(1983・岩波書店) ▽ホール著、岩堀信子訳『数学叢書15 組合せ理論』(1971・吉岡書店) ▽C・ベルジュ著、野崎昭弘訳『組合せ論の基礎』(1973・サイエンス社)』

出典 小学館 日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について 情報 | 凡例

組合せ理論の関連キーワードマルコビッツ有限数学応用数学二項定理

今日のキーワード

阪神園芸

阪神電気鉄道株式会社の子会社で、兵庫県西宮市に本社を置く造園会社。正式名称は「阪神園芸株式会社」。1968年に設立された。環境緑化工事の施工・維持管理、公園植栽などの管理、観葉植物のリースといった業務...

続きを読む

コトバンク for iPhone

コトバンク for Android