重複要素を含むセット** S が与えられた場合、各サブセットが一意である S のすべての可能なサブセットの総数をどのように決定できますか。
たとえば、S = {A, B, B} とし、K をすべての部分集合の集合とすると、K = {{}, {A}, {B}, {A, B}, {B, 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
S が一意の要素のみを持つ実集合である場合、|K| は簡単にわかります。= 2^|S|。
この値 |K| を計算する式は何ですか? すべてのサブセットを生成せずに、「セット」S (重複あり) を指定しますか?
** 技術的にはセットではありません。
すべての（頻度+1）の積を取ります。
たとえば、{A、B、B}では、答えは（1 + 1）[Asの数] *（2 + 1）[Bの数]=6です。
2番目の例では、count（A）= 2およびcount（B）= 2です。したがって、答えは（2 + 1）*（2 + 1）=9です。
これが機能する理由は、任意のサブセットをカウントのベクトルとして定義できるためです。{A、B、B}の場合、サブセットは{A = 0、B = 0}、{A = 0、B=1として記述できます。 }、{0,2}、{1,0}、{1,1}、{1,2}。
counts []の数値ごとに、（そのオブジェクトの頻度+ 1）可能な値があります。（0..周波数）
したがって、可能性の総数はすべての積（頻度+1）です。
「すべて一意」の場合もこのように説明できます。各オブジェクトが1回発生するため、答えは（1 + 1）^ |S|です。= 2 ^ |S|。
この問題は、正しい見方をすれば簡単に解決できると主張します。要素の順序は気にせず、not のサブセットに表示されるかどうかだけを気にします。
セットに各要素が出現する回数を数えます。1 つの要素セット {A} に対して、サブセットはいくつありますか? 明らかに2セットしかありません。ここで、集合 {A,B} を形成するために、A とは異なる別の要素 B を追加したとします。すべてのセットのリストを非常に簡単に作成できます。A のみを使用して形成したすべてのセットを取得し、B のコピーを 0 または 1 つ追加します。実際には、セットの数を 2 倍にします。明らかに帰納法を使用して、N 個の異なる要素の場合、セットの総数がちょうど 2^N であることを示すことができます。
いくつかの要素が複数回出現するとしますか? A のコピーが 3 つあるセットを考えます。したがって、{A,A,A} です。いくつのサブセットを形成できますか? 繰り返しますが、これは簡単です。A のコピーを 0、1、2、または 3 つ持つことができるため、順序は問題にならないため、サブセットの総数は 4 になります。
一般に、要素 A の N 個のコピーの場合、最終的に N+1 個の可能なサブセットになります。ここで、B のコピー数 M を追加してこれを拡張します。つまり、A の N コピーと B の M コピーがあります。総サブセットはいくつありますか? はい、これも明らかです。A のみを含むすべての可能なサブセット (N+1 個あります) に、B の 0 から M のコピーを追加できます。
したがって、A の N 個のコピーと B の M 個のコピーがある場合のサブセットの総数は単純です。(N+1)*(M+1) でなければなりません。繰り返しになりますが、帰納的な議論を使用して、サブセットの総数がそのような項の積であることを示すことができます。個々の要素ごとに複製の総数を数えるだけで、1 を足して積を取るだけです。
セット {A,B,B} で何が起こるかを確認してください。2*3 = 6 が得られます。
セット {A,A,B,B} の場合、3*3 = 9 が得られます。