当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
（平成２７年６月１０日付け）
ｎを正整数とし、S={1，2，3，･･･，ｎ} とする。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 とする。＜こちらの設問は勝手に考えたので正解が何かは未だ分かりません。＞
（答） ａｔ さんが考察されました。（平成２７年６月１０日付け）
前半：「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 個
となりました。
ＧＡＩ さんからのコメントです。（平成２７年６月１１日付け）
よくこんな複雑な式を導けましたね。これによると、
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さんがこの式に至った経緯を聞かせて貰ったら有り難いです。
ａｔ さんからのコメントです。（平成２７年６月１１日付け）
後半部分については、前半部分の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=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つの集合から成るペアの間に等号がある場合をしらみ
つぶしに調べて計算すれば答えが出せます。