重複順列

こんにちは、リンス(@Lins016)です。
今回は重複順列について学習していこう。

重複順列

重複順列とは字の表すとおり、異なるものから重複を許していくつかを並べる順列のことで、異なる\(\small{ \ n \ }\)個の中から重複を許して\(\small{ \ r \ }\)個取り出して並べる重複順列の数は\(\small{ \ n\times n\times n\cdots\times n=n^r \ }\)になる。

重複を許さずに異なる\(\small{ \ n \ }\)個の中から\(\small{ \ r \ }\)個取り出して並べる順列の数は\(\small{ \ {}_n\mathrm{P}_r \ }\)だったよね。

ちなみに教科書には載ってないけど、重複順列の\(\small{ \ n^r \ }\)を記号で\(\small{ \ {}_n \prod_r \ }\)って書いたりもするから大学で数学が必要な人は知っておくといいよ。

自然数を作る重複順列

数を並べる順列で学習したように、重複を許して数を並べる重複順列でも、最高位の数は\(\small{ \ 0 \ }\)にならないように並べないといけない。この点に注意して問題を解こう。

合わせて重複を許さない問題についても復習しておこう。

最高位に\(\small{ \ 0 \ }\)だと桁が変わることに注意して問題を解こう。自然数は\(\small{ \ 1 \ }\)以上の整数だから、\(\small{ \ 0 \ }\)は自然数じゃないことにも注意しよう。

人をグループに分ける重複順列（部屋割り）

今度は人をグループに分ける分け方について考えてみよう。
例えば\(\small{ \ 10 \ }\)人を二つのグループ\(\small{ \ \mathrm{A} \ }\)と\(\small{ \ \mathrm{B} \ }\)に分けるとき、\(\small{ \ \mathrm{A} \ }\)と\(\small{ \ \mathrm{B} \ }\)の人数が違ってもOKとすると、その分け方は\(\small{ \ 2^{10}-2=1022 \ }\)通りある。

これはそれぞれの人\(\small{ \ 10 \ }\)名が\(\small{ \ \mathrm{A} \ }\)と\(\small{ \ \mathrm{B} \ }\)どちらかのグループに入るかって考えると
\(\small{ \ 2\times2\times2\times\cdots\times2=1024 \ }\)通りになる。
だけど、全員が\(\small{ \ \mathrm{A} \ }\)に入る場合と全員が\(\small{ \ \mathrm{B} \ }\)に入る場合は二つのグループに分かれてないから、この\(\small{ \ 2 \ }\)通りを除いた\(\small{ \ 2^{10}-2=1022 \ }\)通りになるんだ。

ちなみにこれって次の考え方もできるから覚えておこう。
\(\small{ \ 10 \ }\)人の中から\(\small{ \ \mathrm{A} \ }\)に入る人を\(\small{ \ 1 \ }\)人選ぶと\(\small{ \ {}_{10}\mathrm{C}_1 \ }\)通り。
もちろん残った\(\small{ \ 9 \ }\)人は全員\(\small{ \ \mathrm{B} \ }\)に入るからね。
\(\small{ \ 10 \ }\)人の中から\(\small{ \ \mathrm{A} \ }\)に入る人を\(\small{ \ 2 \ }\)人選ぶと\(\small{ \ {}_{10}\mathrm{C}_2 \ }\)通り。
\(\small{ \ 10 \ }\)人の中から\(\small{ \ \mathrm{A} \ }\)に入る人を\(\small{ \ 3 \ }\)人選ぶと\(\small{ \ {}_{10}\mathrm{C}_3 \ }\)通り。
\(\small{ \ 10 \ }\)人の中から\(\small{ \ \mathrm{A} \ }\)に入る人を\(\small{ \ 4 \ }\)人選ぶと\(\small{ \ {}_{10}\mathrm{C}_4 \ }\)通り。
　　　　　　\(\small{ \ \vdots \ }\)
\(\small{ \ 10 \ }\)人の中から\(\small{ \ \mathrm{A} \ }\)に入る人を\(\small{ \ 9 \ }\)人選ぶと\(\small{ \ {}_{10}\mathrm{C}_9 \ }\)通り。

つまり\(\small{ \ {}_{10}\mathrm{C}_1+{}_{10}\mathrm{C}_2+\cdots+{}_{10}\mathrm{C}_9 \ }\)通りが\(\small{ \ 10 \ }\)人を二つのグループ\(\small{ \ \mathrm{A} \ }\)と\(\small{ \ \mathrm{B} \ }\)に分ける総数になるよね。

ここで二項定理

に\(\small{ \ n=10,a=1,b=1 \ }\)を代入すると
\(\small{ \ (1+1)^{10}={}_{10}\mathrm{C}_0+{}_{10}\mathrm{C}_1+{}_{10}\mathrm{C}_2+\cdots+{}_{10}\mathrm{C}_{10} \ }\)
\(\small{ \ {}_{10}\mathrm{C}_0={}_{10}\mathrm{C}_{10}=1 \ }\)だから
\(\small{ \ {}_{10}\mathrm{C}_1+{}_{10}\mathrm{C}_2+\cdots+{}_{10}\mathrm{C}_9=2^{10}-2 \ }\)になるよね。
つまり組合せを利用して考えても同じ答えが求まるんだ。求めるものが同じだから当たり前だよね。

よく解答と違うからって考える人がいるけど、組合せを使って答えても正解だからね。
でも二項定理知らずにコンビネーションの和を計算するのってかなり大変だよね。

だから組合せじゃなくて重複順列を利用して簡単に答えを出せるようにしておこう！

ちなみにグループ名を\(\small{ \ \mathrm{A} \ }\)と\(\small{ \ \mathrm{B} \ }\)ってつけずに、ただ二組に分けるだけならこの\(\small{ \ 1022 \ }\)を\(\small{ \ 2! \ }\)で割ればいいからね。

じゃんけんの出し方と重複順列

じゃんけんの出し方も重複順列で考えよう。

例えば\(\small{ \ 4 \ }\)人でじゃんけんする場合、それぞれの人は、グー・チョキ・パーの\(\small{ \ 3 \ }\)通りの出し方があるから、\(\small{ \ 4 \ }\)人でじゃんけんする場合の出し方のは一人目が\(\small{ \ 3 \ }\)通り、二人目も\(\small{ \ 3 \ }\)通り、・・・ってなるから
\(\small{ \ 3\times3\times3\times3=3^4 \ }\)通りになるよね。
つまり重複順列の考え方になるんだ。

ちなみにこのすべての出し方からあいこや勝ち負けが決まる場合について考えてみよう。
\(\small{ \ 3 \ }\)人や\(\small{ \ 4 \ }\)人ぐらいだといいけど、人数が増えていくとあいこを考えるのは難しいよね。
だってあいこは「全員同じものを出す」と「全員バラバラ」があるからね。

\(\small{ \ 10 \ }\)人でじゃんけんするとき、全員バラバラを考えると、グーが何人、パーが何人、チョキが何人って考えないといけなくてかなり計算が大変になるよね。
だからあいこを考えるんじゃなくて勝ち負けが決まる場合を考えよう。
あいこはすべての出し方から勝ち負けが決まる以外を考えたらいいからね。

ちなみに勝ち負けが決まるのはどういう時かというと、全員が二種類を出すときだよね。

つまりグーとパーだけやチョキとパーだけ、チョキとグーだけの\(\small{ \ 3 \ }\)通りあるから、\(\small{ \ n \ }\)人でじゃんけんをするときの勝ち負けが決まる出し方は
\(\small{ \ (2^n-2)\times3 \ }\)通りになるよね。

だからあいこはこれを全体から引けばいいから
\(\small{ \ 3^n-3(2^n-2) \ }\)になるからね。

今回は場合の数だから何通りかを調べたけど、じゃんけんは確率の問題にもよく出題されるから、大人数でじゃんけんする場合のあいこの求め方は覚えておこう。

Point　重複順列

①異なる\(\small{ \ n \ }\)個の中から重複を許して\(\small{ \ r \ }\)個並べるのは\(\small{ \ n^r \ }\)通り
②部屋割り・じゃんけんは重複順列で考える