どのようにして繰り返しとセットからすべての可能なユニークなサブセットの合計数を計算するのですか？

Question

一方が合計数を決定する方法重複要素を含む集合** S、与えられた各部分集合が一意である。S、すべての可能なサブセット

たとえば、S = {A、B、B}は、その後K = {{}、{A}、{B}、{A、B}、{B、Kは、すべての部分集合の集合とすると言いますB}、{A、B、B}}したがって| K | = 6。

別の例は、もしS = {A、A、B、B}、その後、K = {{}、{A}、{B}、{A、B}、{A、A}、{B、あろうB}、{A、B、B}、{A、A、B}、{A、A、B、B}}とそのための| K | = 9

| K |

その後、唯一のユニークな要素を持つ、Sは実際の設定されている場合ことを確認することは容易です= 2 ^ | S |ます。

| K |

この値を計算する式は何ですかすべての部分集合を生成することなく、（重複を有する）「セット」S所与の

**ない技術的にセットます。

Answer 1

すべての（周波数+ 1）の積を取ります。

たとえば、{A、B、B}で、答えは（1 + 1）である[としての数] *（2 + 1）Bsの数] = 6。

第2の例では、（2 + 1）（A）をカウント= 2及び（B）カウント= 2.したがって答えは*（2 + 1）= 9。

、{A、B、B}のために、サブセットは、{A = 0、B = 0}、{A = 0として説明することができる -

これが動作理由は、カウントのベクトルとして任意のサブセットを定義することができるということですB = 1}、{0,2}、{1,0}、{1,1}、{1,2}

カウントの各数について[]（そのオブジェクト+ 1の周波数）の可能な値が存在します。 （0..frequencies）

したがって、possiblitiesの総数は、すべての（周波数+ 1）の積である。

「すべてのユニークな」場合も、この方法を説明することができます - 答えは（1 + 1）^であるように、各オブジェクトの1つの出現がある| S | = 2 ^ | S |ます。

Answer 2

私は、適切な方法で見たときに、この問題は、解決するのは簡単であると主張するでしょう。あなたは、彼らがいないのサブセットに表示されるかどうかだけ、要素の順序を気にしないでください。

各要素がセットに表示された回数をカウントします。 1つの要素集合{A}のために、どのように多くのサブセットがありますか？明らかに2つだけのセットがあります。今、我々は別の要素を追加し、Bは、それが集合{A、B}を形成するために、Aは区別されると仮定する。我々は非常に簡単にすべてのセットのリストを形成することができます。我々は唯一使用して形成されたすべてのセットを取り、実際にはBのゼロまたは1つのコピーに追加し、我々はセット数を倍増します。明らかに、我々はNの異なる要素のため、セットの合計数がわずか2 ^ Nであることを示すために誘導を使用することができます。

いくつかの要素が複数回出現したと？したがって、Aの3つのコピー{A、A、A}のセットを考えます。あなたはどのように多くのサブセットを形成することができますか？繰り返しますが、これは簡単です。我々は、A 0、1、2、または3コピーを有することができるので、順序は重要ではないので、サブセットの総数は4である。

一般的に、元素AのN個のコピーのために、我々は、N + 1つの可能なサブセットで終わるであろう。今、Bのコピーを、いくつかの数、Mに追加することで、これを拡大だから我々は、全サブセットがありますどのように多くのB.のAとMのコピーのN個のコピーを持っていますか？はい、これはあまりにも明確なようです。それだけで持つすべての可能なサブセットに我々はBの0とMコピー間で追加することができます（N +それらの1があった）。

私たちはBのAとMのコピーのN個のコピーを持っている場合、

だから、サブセットの総数は簡単です。これは、（N + 1）*（M + 1）でなければなりません。ここでも、部分集合の総数は、そのような用語の製品であることを示すために、誘導引数を使用することができます。単に、各個別要素のための複製の総数をカウントアップ1を追加し、製品を取る。

集合{A、B、B}で何が起こるかを見ます。私たちは、

2 * 3 = 6を得ます

集合{A、A、B、B}のために、我々は= 9 3 * 3を取得します。