重複を許して並べる順列の基本的な考え方を紹介します．
異なる $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$ 通り．
