重複順列の応用

$${n}$$を$${2}$$以上の整数とする。集合$${\{1,2,…,n\}}$$を互いに共通部分をもたない$${2}$$個の空でない集合に分ける場合の数を求めよ。
                          （同志社大 一部改題）

【実験的考察】
$${n=2}$$のとき、

$$
\{\{1\},\{2\}\}
$$

の$${1}$$通り。
$${n=3}$$のとき、

$$
\{\{1\},\{2,3\}\},\{\{2\},\{1,3\}\},\{\{3\},\{1,2\}\}
$$

の$${3}$$通り。
$${n=4}$$のとき、

$$
\{\{1\},\{2,3,4\}\},\{\{2\},\{1,3,4\}\},\{\{3\},\{1,2,4\}\},\{\{4\},\{1,2,3\}\},\\\{\{1,2\},\{3,4\}\},\{\{1,3\},\{2,4\}\},\{\{1,4\},\{2,3\}\}
$$

の$${7}$$通り。
$${n=5}$$のとき、

$$
\{\{1\},\{2,3,4,5\}\},\{\{2\},\{1,3,4,5\}\},\{\{3\},\{1,2,4,5\}\},\{\{4\},\{1,2,3,5\}\},\{\{5\},\{1,2,3,4\}\},\\\{\{1,2\},\{3,4,5\}\},\{\{1,3\},\{2,4,5\}\},\{\{1,4\},\{2,3,5\}\},\{\{1,5\},\{2,3,4\}\},\\\{\{2,3\},\{1,4,5\}\},\{\{2,4\},\{1,3,5\}\},\{\{2,5\},\{1,3,4\}\},\\\{\{3,4\},\{1,2,5\}\},\{\{3,5\},\{1,2,4\},\{\{4,5\},\{1,2,3\}\}
$$

の$${15}$$通り……。

$${n}$$の値が増えるに従い、どんどん複雑になる上に、方針も今一つ見えてきません。
発想を変えましょう。

【解答】
「$${2}$$個の空でない集合」を集合$${A}$$、集合$${B}$$とする。$${\{1,2,…,n\}}$$の$${n}$$個の数が、自らが属する集合をそれぞれ選ぶとき、その場合の数は、

$$
2^n
$$

このうち、どちらかの集合が空（集合）となるのは

$$
(A,B)=(\{1,2,…,n\},\phi),(\phi,\{1,2,…,n\})
$$

$${2}$$通り。

さらに、集合$${A,B}$$の区別をなくすと、場合の数は半分になるので、求める場合の数は、

$$
\frac{2^n-2}{2}=\underline{2^{n-1}-1(通り)}･･･答
$$

【コメント】
集合が要素を選ぶのではなく、集合の要素が属する集合を選ぶという発想の転換で一気に解決を見ました。
実は、集合$${\{1,2,…,n\}}$$に関して、集合$${A}$$と集合$${B}$$は互いに補集合の関係になっているので、当然のことながら、片方が決まればもう片方もおのずと決まるのでした。
結局のところ、出題者は、集合$${\{1,2,…,n\}}$$の部分集合の個数を問うているわけです。
「部分集合の個数を問われたら、重複順列を考えよ！」
"学びみ"が深いですね。

【使用した公式】
異なる$${n}$$個のものから重複を許して$${r}$$個を取り出して並べる順列を重複順列という。その場合の数は、次の式で得られる。

$$
n×n×n×･･･×n=\prod_{k=1}^{r}n=n^r
$$

左辺は$${n}$$が$${r}$$個並んでかけ合わせれているとみなしてください。
$${\prod}$$（productの頭文字pのギリシャ文字の大文字表記)は$${\sum}$$（summationの頭文字sのギリシャ文字の大文字表記)のかけ算バージョンです。