How do you calculate the total number of all possible unique subsets from a repeat set?

Question

Given a set ** S containing repeating elements, how to determine the total number of all possible subsets of S, where each subset is unique.

For example, say S = {A, B, B} and let K be the set of all subsets, then K = {{}, {A}, {B}, {A, B}, {B, B}, {A, B, B}} and therefore | K | = 6.

Another example: if S = {A, A, B, B}, then K = {{}, {A}, {B}, {A, B}, {A, A}, {B, B }, {A, B, B}, {A, A, B}, {A, A, B, B}} and for this | K | = 9

It is easy to see that if S is a real set having only unique elements, then | K | = 2 ^ | S |.

What is the formula for calculating this value | K | given the “set” of S (with duplicates) without generating all subsets?

** Not technically set.

Answer 1

Take the product of all (frequencies + 1).

For example, in {A, B, B}, the answer is (1 + 1) [As number] * (2 + 1) [Bs number] = 6.

In the second example, count (A) = 2 and count (B) = 2. Thus, the answer is (2 + 1) * (2 + 1) = 9.

The reason for this is that you can define any subset as the vector counts - for {A, B, B}, the subsets can be described as {A = 0, B = 0}, {A = 0, B = 1} , {0,2}, {1,0}, {1,1}, {1,2}.

For each number in count [] there are (frequencies of this object + 1) possible values. (0..frequencies)

Therefore, the total number of possible values ​​is the product of all (frequencies + 1).

" " - , (1 + 1) ^ | S | = 2 ^ | S |.

Answer 2

, , . , .

, . {A}, ? , . , B, A, {A, B}. . , , A, B. , . , , , N 2 ^ N.

, ? A. , {A, A, A}. ? , . 0, 1, 2 3 A, 4, .

N A N + 1 . , B. , N A M B. ? , . A ( N + 1 ) 0 M B.

, , N A M B, . (N + 1) * (M + 1). , , , . , 1 .

, {A, B, B}. 2 * 3 = 6.

{A, A, B, B} 3 * 3 = 9.