重複順列の意味と例題

重複順列の公式

異なる nn 種類のものから、重複を許して rr 個取り出して並べる順列の個数は nrn^r

「重複を許して」というのは「同じものを何度選んでもよい」という意味です。

重複順列の例題

アルファベットの個数

例題1

a,b,ca,b,c から重複を許して 22 個取って並べる順列の総数は何通りか?

解答

重複順列の公式で n=3,r=2n=3,r=2 の場合なので 32=93^2=9 通り。

ちなみにすべて列挙すると, aa,ab,ac,ba,bb,bc,ca,cb,ccaa,ab,ac,ba,bb,bc,ca,cb,cc99 通り。

別解(公式を使わない解答)
  • 1個目に a,b,ca,b,c のどれを選ぶかで 33 通り
  • そのそれぞれについて,2個目に a,b,ca,b,c のどれを選ぶかで 33 通り

結局 3×3=93\times 3=9 通り。

整数の個数

例題2

11 から 99 までの数字を使って作れる3桁の整数は何通りか? (同じ数字を何回使っても良い)

解答

重複順列の公式で n=9,r=3n=9,r=3 の場合なので 93=7299^3=729 通り。

別解(公式を使わない解答)

重複順列

  • 1桁目に 1199 のどれを選ぶかで 99 通り
  • そのそれぞれについて,2桁目に 1199 のどれを選ぶかで 99 通り
  • そのそれぞれについて,3桁目に 1199 のどれを選ぶかで 99 通り

結局 9×9×9=7299\times 9\times 9=729 通り。

公式の証明

さきほどの例題1,2で見た「公式を使わない解答」を一般的に書くだけです。

一般的な公式の証明
  • 1番目に nn 種類のどれを選ぶかで nn 通り
  • そのそれぞれに対して,2番目に nn 種類のどれを選ぶかで nn 通り

ここまでで n2n^2 通り

  • そのそれぞれに対して,3番目に nn 種類のどれを選ぶかで nn 通り

ここまでで n3n^3 通り

これを rr 番目まで繰り返すと nrn^r 通りになる。

関連する話題

重複順列は簡単ですが,少し状況が変わるだけで難しくなります。

nrn^rrnr^n か迷ってしまうので公式丸暗記はオススメしません。毎回意味を考えて「公式を使わない解答」が書けるのがよいです。