集合の集合                                戻る

 当HPがいつもお世話になっているHN「GAI」さんからの出題です。
                                      (平成27年6月10日付け)

 nを正整数とし、S={1,2,3,・・・,n} とする。Sの部分集合A、B、C、D(空集合Φでもよい。)
で、A∪B∪C∪D=S  かつ A∩B∩C=Φ を満たす集合の組(A,B,C,D)は何通りあるか?
 ただし、A、B、C、Dは、同じものが重なっていてもいいものとする。

 また、上の条件を A、B、C、D が全て異なったものに制限すると何通りとなるか?
 ただし、n≧2 とする。<こちらの設問は勝手に考えたので正解が何かは未だ分かりません。



































(答) at さんが考察されました。(平成27年6月10日付け)

前半:「A∪B∪C∪D=S  かつ A∩B∩C=Φ」を満たす集合の組(A,B,C,D)の総数は、
   13n

後半:「A∪B∪C∪D=S  かつ A∩B∩C=Φ かつ A、B、C、D はすべて異なる」を満たす
   集合の組(A,B,C,D)の総数は、13n - 3・5n - 3・6n + 9・2n + 2 個

となりました。


 GAI さんからのコメントです。(平成27年6月11日付け)

 よくこんな複雑な式を導けましたね。これによると、

n=2-->24
n=3-->1248
n=4-->22944
n=5-->338880
n=6-->4640544
・・・・・・・・

となるんですね。n=2の場合は部分集合が4つなので、A、B、C、Dの決め方は、4!=24 とすぐ
に決まるんですが、n=3以上になると部分集合の数が一気に膨らんでいくので、例えば、n=3
でも決められたと思っても、全体を見渡すと重複している物を数えていたりと、思ったより複
雑だと感じていました。atさんがこの式に至った経緯を聞かせて貰ったら有り難いです。


 at さんからのコメントです。(平成27年6月11日付け)

 後半部分については、前半部分の13nから、A、B、C、Dのうちの少なくとも2つの集合が一
致しているようなものを差し引くことによって答えを導きました。

 前半の「13n」は、次のように考えて導きました。

 A∪B∪C∪D=Sを満たす集合の組(A,B,C,D)の個数から、A∪B∪C∪D=S かつ
A∩B∩C≠Φ を満たす集合の組(A,B,C,D)の個数を差し引けばいいです。これを包除原
理を使って計算します。

 A∩B∩Cが、Sのn個の元のうちの特定のk個(0≦k≦n)の元を含むような場合を考えます。
Dは特定のk個の元の各々を含んでいてもいいし、含んでいなくてもいい。その方法は、2k
通り。

 特定のk個以外の(n-k)個の元については、その各々は、A、B、C、Dのうちの少なくとも一
つの集合に含まれていなくてはならない。その方法は、 (24 - 1)n-k 通り。

 また、特定のk個の元の選び方は、 通り。

 以上のことを考えて、求める場合の数は包除原理を使って、

    Σ k=0〜n (-1)k・2k・(24 - 1)n-k=(24-1+(-2))n=13n

となります。

 後半は、A∪B∪C∪D=S かつ A∩B∩C=Φをみたす集合の組(A,B,C,D)の個数から、
A、B、C、Dのうちの少なくとも2つの集合が一致しているようなものを差し引きます。ここでも
包除原理が有効です。

 例えば、A∪B∪C∪D=S かつ A∩B∩C=Φ かつ A=B であるような組(A,B,C,D)の個数
は、A∪C∪D=S かつ A∩C=Φ であるような組(A,C,D)の個数に等しいので、

   Σ k=0〜n (-1)k・2k・(23 - 1)n-k= 5n

です。最後の段階で包除原理を使って計算するときには、その寄与は、 -5n になります。

 また、例えば、A∪B∪C∪D=S かつ A∩B∩C=Φ かつ A=B かつ B=D であるような組
(A,B,C,D)の個数は、A∪C=S かつ A∩C=Φ であるような組(A,C)の個数に等しいので、
2n 個 です。包除原理を使って計算するときには、その寄与は +2n になります。

 さらに例えば、A∪B∪C∪D=S かつ A∩B∩C=Φ かつ A=B かつ B=D かつ A=D である
ような組(A,B,C,D)の個数も同様に 2n 個となります。ただし包除原理を使って計算すると
きには、その寄与は -2n になります。

 以下同様に、A、B、C、Dのうちの2つの集合から成るペアの間に等号がある場合をしらみ
つぶしに調べて計算すれば答えが出せます。