読者です 読者をやめる 読者になる 読者になる

デジタル・デザイン・ラボラトリーな日々

アラフィフプログラマーが数学と物理を基礎からやり直す

順列と組合せを理解してみる-順列

はじめに

前回、順列に入る前に「場合の数」として「積の法則」と「和の法則」を説明しました。 yaju3d.hatenablog.jp

ここで重要なのは「積の法則」で、事象の数がいくつあっても、それが同時に起こる場合は積の法則で場合の数を求めます。

順列とは

順列とは、ひと言で言うと「並べ替え」のことです。 数学的な説明だと「一般に互いに異なる n個のものから r個取り出して、それを1列に並べるとき、その並べ方を、n個のものから r個取る」を順列といいます。
分かりにくいので、実際に問題を説いてみましょう。

問題と解説

1、2、3の3個の数字を並べ替えて3桁の整数を作ります。1度使った数字は2度は使いません。考えうる整数のパターンは何通りできるでしょうか?

積の法則で、 3 \times 2 \times 1 = 6通りとなります。

場合の数が少ないので樹形図で表現してみます。
f:id:Yaju3D:20160710161743p:plain

1度使った数字は2度は使わないため、次の数字のパターンは1つずつ減っていきます。
これは数学の定義では、nの階上(かいじょう) n! として表します。

nの階乗は1から n までの整数を乗算したもので、以下のように展開できます。 n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1

席とは

「並べ替える」というのを視点を変えてみると、下図のように「用意された席に要素を当てはめる」と考えることができます。
f:id:Yaju3D:20160710213741p:plain

n=rの場合

A、B、Cの3人が3つの席に座る方法(順番)は何通りあるか。

「席の問題」では、「席を順番に埋める」ことを考えます。3つの席(n)に3人(r)と n=rの場合となります。

1つ目の席の埋め方は、A、B、Cの3通り。
2つ目の席は、1つ目の席に座った人以外の2通り 。
3つ目の席は、1つ目と2つ目の席に座った人以外(残り)の1通り。

積の法則で、 3! = 3 \times 2 \times 1 = 6通りとなります。

n<rの場合

A、B、C、D、Eの5人が3つの席に座る方法は何通りか。

「席の問題」なので、まず席を順番に埋めてみます。3つの席(n)に5人(r)と n<rの場合となります。

f:id:Yaju3D:20160710222219p:plain

積の法則で、 5 \times 4 \times 3 = 60通りとなります。

順列の計算方法

n<rの場合の計算では、5(=n)から始めて3(=r)個の数を、1ずつ減らしています。
問題の人数(n)や席の数(r)が変わっても、計算の方法は同じです。

順列には下記の公式があります。Pはpermutation(パーミュテーション)の頭文字です。
公式:\displaystyle _n P _r = \frac{n!}{(n-r)!}

_5 P _3 = 5 \times 4 \times 3 (←5から始めて3個かけた)
公式を分解していくと下記のようになります。
=\displaystyle \frac{5!}{(5-3)!}
=\displaystyle \frac{5!}{2!}
=\displaystyle \frac{5 \times 4 \times 3 \times 2 \times 1}{2 \times 1}
=5 \times 4 \times 3 (←分母分子の 2×1 を消した)

n=rの場合も、_3 P _3となります。これは 3!と同じことになります。

重複順列

最初に重複順列の説明をしましたが、もう少し説明を追加してみます。
yaju3d.hatenablog.jp

問題と解説

5題の問題に○、×で答える答え方は何通りあるか。

この例では、「1問目」「2問目」・・「5問目」を「席」と考えます。
このように、要素を何度使ってもよい問題では、「席」の考え方が便利です。

f:id:Yaju3D:20160711002227p:plain

積の法則で、 2 \times 2 \times 2 \times 2 \times 2 = 32通りとなります。
重複順列の公式  n^r を用いて  2^5 = 32 でもいいです。

1問目の答え方は、○か×の2通り。
2問目の答え方も、○か×の2通り。これは1問目の答え方に影響されません。
同じようにして、3、4、5問目の答え方もそれぞれ2通りずつとなります。

順列と重複順列の違い

  • 順列は並び方を考慮する。
  • 重複順列は並び方を考慮せず、選び方のみ。

順列と和の法則

事象の数がいくつあっても、それが同時に起こらない場合は和の法則を使って場合の数を求めます。
今回、順列と和の法則を組合せて場合の数を求めます。

問題と解説

0 から 6 までの7個の数字を取り出して並べるとき、5で割り切れる4けたの整数の個数を求めなさい。

ヒント:5の倍数は一の位が必ず、0か5になることに注意します。

一の位が0の場合と5の場合を別々に考えます。

一の位が0の場合

千の位、百の位、十の位は1から6までの数字を1回づつ使うことができるので、6個の中から3個を取り出し並べる順列の数を求めます。
_6 P _3 = 6 \times 5 \times 4 = 120 通りとなります。

f:id:Yaju3D:20160716164303p:plain

一の位が5の場合

千の位に0が使えないので、千の位は0、5以外の5通り、百と十の位は一と千の位で用いた数字以外どれでも1回づつ使える順列の数を求めます。
5 \times  _5 P _2 = 5 \times 5 \times 4 = 100 通りとなります。

f:id:Yaju3D:20160716164238p:plain

和の法則を使う

ここで、一の位が0の場合と5の場合は同時にはおきないので、和の法則を使用します。
全部で 120 + 100 = 220 通りとなります。

円順列

順列には円順列というのもあります。

問題と解説

4人の生徒が円形のテーブルのまわりに座るとき、座り方は何通りあるか?

順列と同様に並び方だけなら、4! = 24 通りになります。順列と円順列の違いはここからです。

f:id:Yaju3D:20160716170514p:plain

これら4つの並び方は、回転させることによって重なるので、どれも同じ1つの並び方だと考えられる。
つまり、上図の①,②,③,④のように順送りに並ぶ4つの順列は、円形に並べた場合には同一視とします。
よって、この4人の座り方は \displaystyle \frac{4!}{4} = 3! = 6 通りとなります。

\displaystyle \frac{4!}{4} = (4 - 1)!と変換できますので、円順列の公式は (n - 1)!で表します。

数珠順列

数珠順列は「じゅず順列」と読みます。回転したりひっくり返しても一致しない円状の配列を数珠順列といいます。

問題と解説

A・B・C・Dに紐を通してネックレスを作るとき、作り方の場合の数を求めよ

並び方だけなら円順列と同じなので、(4 - 1)! = 3! = 6 通りとなります。円順列と数珠順列の違いはここからです。

f:id:Yaju3D:20160716173715p:plain

上図のようにネックレスなので裏返しても同じになることがあります。
このように表裏をひっくり返すことができる場合には、同一視とします。
よって、2で割るため、\displaystyle \frac{ (4 - 1)! }{2} = 3 通りとなります。

参考