@niftyトップ

辞書、事典、用語解説などを検索できる無料サービスです。

順列・組合せ【じゅんれつくみあわせ】

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

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

n個の異なるものからr個を取り出して1列に並べたものをn個からr個とる順列といい、その総数をnPrと書く(Pは、順列の英語permutationの頭文字をとったもの)。たとえば、4個の文字A、B、C、Dから3個をとって並べると、次のような24通りの順列ができる。したがって、4P3=24である。

  ABC ABD ACB ACD ADB ADC
  BAC BAD BCA BCD BDA BDC
  CAB CAD CBA CBD CDA CDB
  DAB DAC DBA DBC DCA DCB
 順列は、図Aのような樹形図を書くと考えやすい。一般に「二つの事柄A、Bがあって、Aのおこり方がm通りあり、そのおのおのに対して、Bのおこり方がn通りずつあれば、AとBが引き続いておこる場合の数はm×nである」が成り立つ。これを積の法則というが、このことから図Aによって容易にわかるように4P3=4×3×2が得られ、一般に

となる。この式の右辺は、

と変形できるから、階乗!を用いると、

と表される。とくにn個からn個とる順列、すなわち、n個の異なるものを1列に並べてできる順列の総数はnPnn!である。

 n個の異なるものからr個を取り出してできる各組を、n個からr個とる組合せといい、その総数をnCrまたは

と書く(Cは、組合せの英語combinationの頭文字をとったもの)。これは順列において順序を考えに入れない場合である。たとえば、4個の文字A、B、C、Dから3個をとってできる組合せは
  {A, B, C},{A, C, D},{A, B, D},{B, C, D}
の4通りである。したがって4C3=4である。この値は次のように4P3からも求められる。4P3個の順列のなかには、組合せとして同じものが3P3=3!=6個ずつ含まれている。したがって4P3=3!4C3ゆえに
  4C34P3/3!=24/6=4
一般に、nPrnnCrが成り立ち、

この式でr=0とすれば、形式的に

が得られる。nCrn個の要素からできている集合の部分集合でr個の要素をもつものの総数に等しい。nC0はそれらの部分集合のなかの「要素をもたないもの」すなわち空集合を1個と数えたことに相当する。

[植竹恒男]

組合せに関する公式

1枚の硬貨を6回投げるとき、表が2回だけ出る場合は何通りあるか考えてみよう。1、2、……、6回目に出た結果を図Bのように書き入れていくと、これらの六つの枠のうちから二つを選んで「表」と記入し、残りは「裏」とすれば、条件に適する組合せが一つできる。よって、求める場合の数は6C2=(6・5)/2!=15となる。この問題は、六つの枠から四つを選んで「裏」と記入し、残りを「表」と考えて、6C4=(6・5・4・3)/4!=15としても解ける。同様に考えて、一般に
  nCrnCn-r
が成り立つ。また、次の等式も成り立つ。

  n-1Crn-1Cr-1nCr
 図Cのように、この関係を利用してnCrの値を順次求めていくのがパスカルの三角形である。

[植竹恒男]

いろいろな順列

A、B、C、Dの4人が丸テーブルに着席する仕方は全部で何通りあるだろうか。この場合は図Dのように、4人が一つずつ順送りに位置を変えてできる四つの並び方はすべて同じものとみられる。図Dのように、一番上から始めて時計と逆回りにとった四つの順列をABCD, DABC, CDAB, BCDAで表す。4人が1列に並ぶ順列の数4!=24のなかには、このような意味で「同じ」順列が四つずつあるから、求める場合の数は4!/4=3!=6となる。一般に、n人が丸テーブルに着席する仕方は全部でn!/n=(n-1)!通りある。また、n人からr人を選んでこのように並ぶ仕方は全部でnPr/r通りある。このような順列を円順列という。n個の玉で数珠(じゅず)やネックレスをつくる場合は、さらに図Dを裏返しにしたものも「同じ」とみなされるから、円順列の数の半分になる。このような順列を数珠順列とよぶ。

 4個の文字A、B、C、Dから3個の文字を取り出して並べる場合、同じ文字を何回使ってもよいとすれば、どの文字についても4通りの選び方があるから、全部で4×4×4=43=64通りあることになる。一般に、n個の異なるものから同じものを重複してとることを許してr個とる順列を重複(ちょうふく)順列といい、その総数はnrとなる。

[植竹恒男]

『C・L・リウ著、伊理正夫他訳『組合せ数学入門Ⅰ』(1972・共立全書)』

出典:小学館 日本大百科全書(ニッポニカ)
(C)Shogakukan Inc.
それぞれの解説は執筆時点のもので、常に最新の内容であることを保証するものではありません。

順列・組合せ」の用語解説はコトバンクが提供しています。

順列・組合せの関連情報

他サービスで検索

(C)The Asahi Shimbun Company /VOYAGE MARKETING, Inc. All rights reserved.
No reproduction or republication without written permission.

アット・ニフティトップページへ アット・ニフティ会員に登録

ウェブサイトの利用について | 個人情報保護ポリシー
©NIFTY Corporation