日本大百科全書(ニッポニカ) 「順列・組合せ」の意味・わかりやすい解説
順列・組合せ
じゅんれつくみあわせ
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、Bがあって、Aのおこり方がm通りあり、そのおのおのに対して、Bのおこり方がn通りずつあれば、AとBが引き続いておこる場合の数はm×nである」が成り立つ。これを積の法則というが、このことからによって容易にわかるように4P3＝4×3×2が得られ、一般に
となる。この式の右辺は、
と変形できるから、階乗！を用いると、
と表される。とくにn個からn個とる順列、すなわち、n個の異なるものを1列に並べてできる順列の総数はnPn＝n！である。
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ゆえに
4C3＝4P3/3！＝24/6＝4
一般に、nPr＝n！nCrが成り立ち、
この式でr＝0とすれば、形式的に
が得られる。nCrはn個の要素からできている集合の部分集合でr個の要素をもつものの総数に等しい。nC0はそれらの部分集合のなかの「要素をもたないもの」すなわち空集合を1個と数えたことに相当する。
［植竹恒男］
組合せに関する公式
1枚の硬貨を6回投げるとき、表が2回だけ出る場合は何通りあるか考えてみよう。1、2、……、6回目に出た結果をのように書き入れていくと、これらの六つの枠のうちから二つを選んで「表」と記入し、残りは「裏」とすれば、条件に適する組合せが一つできる。よって、求める場合の数は6C2＝(6・5)/2！＝15となる。この問題は、六つの枠から四つを選んで「裏」と記入し、残りを「表」と考えて、6C4＝(6・5・4・3)/4！＝15としても解ける。同様に考えて、一般に
nCr＝nCn-r
が成り立つ。また、次の等式も成り立つ。
n-1Cr＋n-1Cr-1＝nCr
のように、この関係を利用してnCrの値を順次求めていくのがパスカルの三角形である。
［植竹恒男］
いろいろな順列
A、B、C、Dの4人が丸テーブルに着席する仕方は全部で何通りあるだろうか。この場合はのように、4人が一つずつ順送りに位置を変えてできる四つの並び方はすべて同じものとみられる。のように、一番上から始めて時計と逆回りにとった四つの順列をABCD, DABC, CDAB, BCDAで表す。4人が1列に並ぶ順列の数4！＝24のなかには、このような意味で「同じ」順列が四つずつあるから、求める場合の数は4！/4＝3！＝6となる。一般に、n人が丸テーブルに着席する仕方は全部でn！/n＝(n-1)！通りある。また、n人からr人を選んでこのように並ぶ仕方は全部でnPr/r通りある。このような順列を円順列という。n個の玉で数珠(じゅず)やネックレスをつくる場合は、さらにを裏返しにしたものも「同じ」とみなされるから、円順列の数の半分になる。このような順列を数珠順列とよぶ。
4個の文字A、B、C、Dから3個の文字を取り出して並べる場合、同じ文字を何回使ってもよいとすれば、どの文字についても4通りの選び方があるから、全部で4×4×4＝43＝64通りあることになる。一般に、n個の異なるものから同じものを重複してとることを許してr個とる順列を重複順列(ちょうふくじゅんれつ)といい、その総数はnrとなる。
［植竹恒男］
『C・L・リウ著、伊理正夫他訳『組合せ数学入門Ⅰ』（1972・共立全書）』
