(9) A, B, Cの3つのグループに分ける。 (10) 3つのグループに分ける。 (9) は、区別された3つのグループA, B, Cに分ける問題です。 (10)は、区別されない3つのグループに分ける問題です。 ただし、それぞれ分ける対象の数についての記述がないため、対象の数が不明です。 ここでは、n個のものを分けるという前提で考えます。 また、それぞれのグループに最低1つは入るものとします。

1. 問題の内容

(9) A, B, Cの3つのグループに分ける。 (10) 3つのグループに分ける。

(9) は、区別された3つのグループA, B, Cに分ける問題です。

(10)は、区別されない3つのグループに分ける問題です。

ただし、それぞれ分ける対象の数についての記述がないため、対象の数が不明です。

ここでは、n個のものを分けるという前提で考えます。

また、それぞれのグループに最低1つは入るものとします。

2. 解き方の手順

(9) n個のものを区別された3つのグループA, B, Cに分ける方法の総数を考えます。

各要素について、A, B, Cのいずれかのグループに属するため、各要素に対して3通りの選択肢があります。

したがって、n個の要素を3つのグループに分ける方法は $3^n$ 通りです。

ただし、すべての要素が同じグループに入ってしまう場合（Aのみ、Bのみ、Cのみ）を除外する必要があります。

また、少なくとも1つの要素が各グループに属するようにする必要があります。

包除原理を使うと、

$3^n - 3 \cdot 2^n + 3 \cdot 1^n$

これは、3つのグループそれぞれが空集合にならないようにする方法の数です。

(10) n個のものを区別されない3つのグループに分ける方法の総数を考えます。

これは(9)の結果をグループの区別をなくすために $3! = 6$ で割れば良いというわけではありません。

なぜなら、各グループの要素数が異なる場合とそうでない場合があるからです。

ここではnが小さい場合について具体的に考えます。

例えば、n=3の場合、{1}, {1}, {1}と分ける方法は1通り、{2}, {1}, {0}と分ける方法は0通り (0は許可されていない)、{3}, {0}, {0}と分ける方法は0通り。

n=4の場合、{2},{1},{1} と {2},{2},{0} と {3},{1},{0} と {4},{0},{0}。

n=5の場合、{3},{1},{1} と {2},{2},{1} と {4},{1},{0} と {5},{0},{0}。

n=6の場合、{2},{2},{2} と {4},{1},{1} と {3},{2},{1} と {5},{1},{0} と {6},{0},{0}。

n個のものを区別されないk個のグループに分ける方法の数は、分割数を用いて表されます。

分割数p(n, k)は、nをk個以下の自然数の和で表す方法の数です。

ただし、各グループに少なくとも1つ入るようにするには、分割数p(n, k)を用いる必要があります。

ベル数を考えると、少なくとも１つは入るという条件をつけないと、空集合も考慮に入れることになってしまいます。

3. 最終的な答え

(9) $3^n - 3 \cdot 2^n + 3$ 通り

(10) n個のものを区別されない3つのグループに分ける方法は、分割数p(n, 1) + p(n-1, 2) + p(n-2, 3) 通りです。

もしくは、第二種スターリング数を用いて表すことができます。この問題の場合、S(n, 1) + S(n, 2) + S(n, 3) となります。

しかし、分割数を用いる方が分かりやすいでしょう。

例えば、n=6の時、p(6,1) + p(5,2) + p(4,3) = 1 + 2 + 1 = 4 となります。

{4,1,1}, {3,2,1}, {2,2,2}

これらを並べ替えると、{2,2,2} (1), {4,1,1} (3), {3,2,1} (6)。

このうち、少なくとも１つは入るという条件を満たさない場合を除くことになります。

そして、グループに区別がないので、並べ替えて同じになるものを除く必要があります。

第二種スターリング数を使うとS(6,1) + S(6,2) + S(6,3) = 1 + 31 + 90 = 122。これは明らかに違う。

包除原理を使うと、(3^6 - 3*2^6 + 3)/6 = (729 - 192 + 3) / 6 = 540/6 = 90。これも違う。

したがって、(9)は $3^n - 3 * 2^n + 3$

(10)は分割数または第二種スターリング数を用いて表すことができますが、具体的な数値を求めるのは難しいです。

分割数を用いる場合はp(n,1)+p(n-1,2)+p(n-2,3)となります。