基礎的な数え上げの範疇 - 現代の量子力学

基礎的な数え上げの範疇です。

部分集合の数を数え上げたい

要素がK個（以下サイズがKという）の集合Sの部分集合の数は、 $2 ^ K$ である（空集合を含む）。これはそれぞれの要素について、その要素が部分集合に入るか？入らないか？の2 通りあり、その選び方は他の要素をどう選んだかに影響されない（独立である）ので全てかけあわせることで求められる。

・部分集合の選び方に制限がある場合
例えば、Sのある部分集合Aのうちからは1 つまでしか選べないという条件がついたとする。すると、A内の要素を選ぶ際には上と同様には選べない。具体的にはAのサイズをX（X <= K）とすると、Aの要素を部分集合に選ぶ選び方は、簡単にX+1 通り。1 はAの要素から1 つも選ばないというパターン。

他の要素の選び方はAの選び方には影響しないし、Aの選び方も他の要素の選び方には影響しない（独立）。ので、他の要素の選び方は上と同様にして、答えは $(X+1) * 2 ^ {K - X}$ とできる。

Aみたいな集合が複数あるならそれぞれについて場合の数を出して最後に掛け合わせれば良い。（条件なしの問題はサイズ1 の部分集合AがK個ある場合とも言える）

・E - ∙ (Bullet)
一緒に選んではいけない要素の組がいくつかある、という条件。

例えば、サイズXの部分集合Aの要素とサイズYの部分集合Bの要素は一緒に選んではいけないとする。A, B から条件を満たすように選び出す場合の数は、Aからのみ選ぶパターン $2 ^ X$ とBからのみ選ぶパターン $2 ^ Y$ を足し、どちらからも選ばないパターンを両方で数えているので1 引いて、 $2 ^ X + 2 ^ Y - 1$ となる。

別の一緒には選んではいけない部分集合の組の選び方とは独立なので、全ての組について場合の数を出し、かけあわせる。

まとめ

何が独立かを考えてそれぞれについて場合の数を求めてかけあわせる。基礎的な数え上げの範疇でした。反省。