順列

コード例

#include <bits/stdc++.h>

using namespace std;

int main() {
  vector<int> v = {3, 4, 3, 1};

  // next_permutation()を呼び出す前に昇順にソートしておく必要がある
  sort(v.begin(), v.end());

  do {
    for (auto x : v) {
      cout << x << " ";
    }
    cout << endl;
  } while (next_permutation(v.begin(), v.end()));
}

1 3 3 4
1 3 4 3
1 4 3 3
3 1 3 4
3 1 4 3
3 3 1 4
3 3 4 1
3 4 1 3
3 4 3 1
4 1 3 3
4 3 1 3
4 3 3 1

解説/アルゴリズム

異なる n 個のものから r 個を取り出して並べたものを、n個からr個とった順列といい、順列の総数を ${}_n \mathrm{P} {}_r$ と表す。

たとえば ${}_5 \mathrm{P} {}_3$ の場合、異なる 5 個のものから 3 個を取り出すという意味になる。

最初の 1 個を取り出すとき、5 通りの選び方がある。

次の 1 個を取り出すとき、既に 1 個取り出しているので、余った 4 個の中から選ぶ 4 通りの選び方がある。

次の 1 個を取り出すとき、既に 2 個取り出しているので、余った 3 個の中から選ぶ 3 通りの選び方がある。

選び方は前の選択に依存しているので積の法則により、 5 x 4 x 3 = 60通り 、つまり ${}_5 \mathrm{P} {}_3 = 60$ になる。

次は一般化して式を考えてみる。

${}_n \mathrm{P} {}_r$ の場合、最初に取り出せるのはn個、次に取り出せるのはn - 1個、更に次に取り出せるのはn - 2個なので、 $n(n-1)(n-2)\thinspace...$ と n の値を減らして掛け算をしていく。

取り出すのはr個なので掛け算の最後の因子はn - r + 1、まとめると下記の式になる。

${}_n \mathrm{P} {}_r = n(n-1)(n-2)...(n-r+1)$

式の変形

たとえば $_{10} \mathrm{P} _{3}$ は 10 x 9 x 8 のことだが、これは10!から7!を割ったものと考えることができ、 7 は 10 - 3 から出てきているので、 ${}_{10} \mathrm{P} {}_{3} = \dfrac{10!}{(10-3)!}$ と書き換えることができる。

一般化すると、 ${}_n \mathrm{P} {}_r = \dfrac{n!}{(n-r)!}$ になる。

円順列

ものを円形に並べる順列を円順列と呼ぶ。

回転させたときに位置が一致するならば、並び方が同じであると考える。 たとえばテキストで並べたABCDならば、BCDA, CDAB, DABCも同じ並びになる。

4 つの席がある場合 $_4 \mathrm{P} _4$ 通りの並び方があるが、上記の説明の通り、回転させた場合も同じ並びになるので、 4 で割った $\dfrac{_4 \mathrm{P} _4}{4} = \dfrac{4!}{4} = 3!$ になる。

一般化すると $\dfrac{_n \mathrm{P} _n}{n} = \dfrac{n!}{n} = (n-1)!$ 通りとなる。

重複順列

一度選んだものでも繰り返して使用していい順列を重複順列と呼ぶ。

たとえば 0 ～ 9 の数字 10 通りを使って 3 桁の数字を作る場合、 1 つ目の桁は 10 通り、 2 つ目の桁も 10 通り、 3 つ目の桁も 10 通り使用できるので、 $10 \times 10 \times 10 = 1000$ 通りの組み合わせがある。

一般化すると、 n 個から r 個とる重複順列の総数は $n^r$ 通りとなる。

選んだものは次の選択で減るわけではないので、 $n < r$ になる場合もある。

関連記事

• 階乗
• 組み合わせ