重複を許して並べる順列の基本的な考え方を紹介します.
異なる $n$ 個のものから異なる $r$ 個を取り出して並べる順列の総数は ${}_n \mathrm{P}_r$ でした.(→順列の基礎)では,異なる $n$ 個のものから,重複を許して $r$ 個選んで並べる順列の総数はいくつになるでしょうか.『重複を許して』というのは,同じものを何度でも選んでよいという意味です.
たとえば,$A,B,C$ という $3$ 種類の記号があるとき,これらから重複を許して $2$ 個並べる方法は,下のように $9$ 通りあります. \begin{array}{ccc} AA&AB &AC \\ BA&BB &BC \\ CA&CB &CC \\ \end{array} 同様に,重複を許して $3$ 個並べる方法は,下のように $27$ 通りあります. \begin{array}{ccccccccc} AAA&AAB&AAC&ABA&ABB&ABC&ACA&ACB&ACC \\ BAA&BAB&BAC&BBA&BBB&BBC&BCA&BCB&BCC \\ CAA&CAB&CAC&CBA&CBB&CBC&CCA&CCB&CCC \\ \end{array} さて,一般に異なる $n$ 個のものから,重複を許して $r$ 個選んで並べる順列の総数はいくつでしょうか.
つぎのように考えてみましょう.まず,$r$ 個のマスを一列に並べたものを用意しておいて,この各マスに $n$ 個のものを左から順に入れていくことにします.
まず,一番左端には $n$ 個のどれを入れてもよいです.そのそれぞれの場合について,左から二番目のマスにも $n$ 個のどれを入れてもよいです.(重複して並べることを許されているので) 以後,ずっと同じように,どのマスにも $n$ 個のどれを入れてもよいです.つまり,前のマスに何を入れたかに関係なく,各マスには $n$ 個のどれを入れてもよいのです.したがって,積の法則から次の公式が成り立ちます.
重複順列の総数: 異なる $n$ 個のものから $r$ 個選んで並べる重複順列の総数は $\large n^r$
重複順列の考え方を応用して,組分けの問題を解いてみましょう.
例題 赤,青,黄,緑,紫色の $5$ つの球がある. (1) $5$ つの球を $2$ つの箱 $X,Y$ にいれる方法は何通りあるか.ただし,ひとつの球も入っていない箱があってもよいとする. (2) $5$ つの球を $2$ つの箱 $X,Y$ にいれる方法は何通りあるか.ただし,どの箱にも少なくともひとつは球が入っているとする.
(3) $5$ つの球をふたつの組に分ける方法は何通りあるか.
いま,知りたいのは (3) の,『$5$ つの球をふたつの組に分ける方法が何通りあるか』という問題です.(これが組分けと呼ばれる問題です)しかし,いきなり (3) を考えるのは難しいので,まず,(1),(2) を解いて,それから (3) を解くという方針です. (1) 各色の球に $X$ または $Y$ を割り当てることを考えます.この割り当て方の総数と $X,Y$ から $5$ 個選んで並べる重複順列の総数は等しいです.したがって割り当て方の総数は $\boxed{2^5=32}$ 通りです. (2) (1) での割り当て方に対して,すべての球に $X$ を割り当てる場合と,すべての球に $Y$ を割り当てる場合の $2$ 通りのみが (2) の条件を満たしません.したがって,$\boxed{2^5-2=30}$ 通り. (3) (2) と (3) の違いは,箱の区別があるかないかです.たとえば,(2) で,下図のような $2$ つの場合を考えます.
この $2$ つの場合は (3) ではひとつの分け方となります.なぜなら,(3) ではどのように分けられているかのみが問題だからです.このように,(2) の $2$ つの場合が (3) の $1$ つの場合に対応します.
したがって,求める場合の数は, $$\frac{30}{2}=15$$ $\boxed{15}$ 通りです.
上の考察のように組分けの問題は,まず区別のある箱に分ける方法を考えて,そのあとで箱の区別をなくす,という手順で考えます.この考え方を一般化すると,次の公式が得られます.
組分けの個数: 異なる $n$ 個のものを $2$ つの組に分ける方法は $\large \frac{2^n-2}{2}=2^{n-1}-1$ 通り.
問 集合 $X=\{1,2,3,4\}$ の部分集合の個数を求めよ.
$1,2,3,4$ のそれぞれについて,部分集合に入れるか,入れないかの $2$ 通りが考えられる.したがって,部分集合の個数は $$2^4=16$$ $16$ 通り.(すべて部分集合に入れない場合は空集合となるが,これも部分集合のうちのひとつであることに注意)
問 $0,1,2,3,4,5$ の $6$ 種類の数字を用いて,$4$ 桁の整数はいくつつくれるか.
千の位として選べる数字は $1,2,3,4,5$ の $5$ 通り.百,十,一の位として選べる数字はいずれも $0,1,2,3,4,5$ の $6$ 通り.したがって, $$5\times 6\times 6\times 6=1080$$ $1080$ 個つくることができる.
問 $A,B,C,D,E,F$ の $6$ 人を $2$ つのグループに分ける方法は何通りあるか.
$$\frac{2^6-2}{2}=31$$ $31$ 通り.