Distribution in sets and subsets

Question

Suppose we have a set $S$ with two elements, $$S=\{A,B\}$$ Now the subsets are $2^2$, I am going to make a new set and call it $S_1$, $$S_1=\{\{\},\{A\},\{B\},\{A,B\}\}$$ There are $2^4$ subsets for $S_1$ yet I am going to eliminate the empty set and re-define my $S_1$ as: $$S_{1_{new}}=\{\{A\},\{B\},\{A,B\}\}$$ for $S_{1_{new}}$ there are 8 subsets. I shall repeat the procedure $n$ times in similar manner. Now I am wondering how many A and B I will have in the set $n$-th.

Another question is that suppose my original set $S$ has N elements how will this be generalised?

Answer 1

The size of the power set of a set with $N$ members is $2^N$.

Thus, assuming the original set does not contain the empty set, the size of $S_n$ is simply

$$\#(S_n) = 2^{\#(S_{n-1})}-1$$

Because it is simply the power set of the previous set with the null set, a single element, removed.

That recurrence applies to the general case.

Answer 2

This post discusses only the "counting how many $A$s" part of the question. @William clarified that:

$$S_{2_{new}} = \{ \{\{A\} \}, \{ \{B\}\}, \{ \{A,B\}\}, \{\{A\},\{B\}\}, \{\{A\},\{A,B\}\}, \{\{B\},\{A,B\}\}, \{\{A\}, \{B\}, \{A,B\}\} \}$$

has 7 elements and he would like to count this as having 8 $A$s, i.e., the total no. of $A$s in the nesting structure. It seems to me this count $f()$ can be captured by this definition:

• $f(A) = 1, \ \ \ f(B) = f(C) = \cdots = 0$,
• For any set $\mathbb{X}, f(\mathbb{X}) = \sum_{x \in \mathbb{X}} f(x)$.

Now consider any set $\mathbb{X}$. Each $x \in \mathbb{X}$ appears in exactly $2^{|\mathbb{X}|-1}$ subsets $\mathbb{Y} \subset \mathbb{X}$. (I.e. $x$ appears in exactly half the subsets, if you count the empty subset.) Now consider the power set:

$$f(2^{\mathbb{X}}) = \sum_{\mathbb{Y} \in 2^{\mathbb{X}}} f(\mathbb{Y}) = \sum_{\mathbb{Y} \subset \mathbb{X}} f(\mathbb{Y}) = \sum_{\mathbb{Y} \subset \mathbb{X}} \sum_{x \in \mathbb{Y}} f(x)$$

Each $x$ appears in $2^{|\mathbb{X}|-1}$ of the $\mathbb{Y}$s, and in each appearance it contributes $f(x)$ to the sum. Since this is true for any $x$, we have:

$$f(2^{\mathbb{X}}) = \sum_{\mathbb{Y} \subset \mathbb{X}} \sum_{x \in \mathbb{Y}} f(x) = 2^{|\mathbb{X}|-1} \sum_{x \in \mathbb{X}} f(x) = 2^{|\mathbb{X}|-1} f(\mathbb{X}). $$

Denote $\mathbb{X}_{new} = 2^{\mathbb{X}} - \{\emptyset\}$ and clearly the count doesnt change:

$$f(\mathbb{X}_{new}) = f(2^{\mathbb{X}} - \{\emptyset\}) = f(2^{\mathbb{X}}) = 2^{|\mathbb{X}|-1} f(\mathbb{X})$$

This is the general recurrence. It looks simple but the complication is actually in the recurrence for size $|\mathbb{X}|$, which as @Austin pointed out, is non-trivial because you drop the empty set every iteration.

Some numbers if you start with just $\{A, B\}$:

• $f(S_{2new}) = 2^{|S_{1new}|-1} f(S_{1new}) = 2^{3-1} \times 2 = 8$,
• $f(S_{3new}) = 2^{|S_{2new}|-1} f(S_{2new}) = 2^{7-1} \times 8 = 2^9$, etc.