2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Re: counting how many $A$: If I understand you correctly then $$S_{2_{new}} = \{ \{\{A\} \}, \{ \{B\}\}, \{ \{A,B\}\}, \{\{A\},\{B\}\}, \{\{A\},\{A,B\}\}, \{\{B\},\{A,B\}\}, \{\{A\}, \{B\}, \{A,B\}\}$$ which has 7 elements, right? How many $A$s would you say are in here? Depending on your definition it may be 0 (none of the 7 is $A$), 6 (6 out of the 7 has some $A$ somewhere nested), or 8 (if you count each "appearance" of $A$ in the nesting). $\endgroup$ – antkam Apr 6 '18 at 14:03
  • $\begingroup$ @antkam I'm counting each appearance. but you're right now how many A's are gonna be there if you go to $S_{n_{new}}$. Also if you have $S={A,B,C,....}$ what would it be in that case $\endgroup$ – Wiliam Apr 6 '18 at 14:14
  • $\begingroup$ In other words you are looking for a closed form for $T(n)$ where $T(2)=3$ and $T(n+1)=-1+2^{T(n)}.$ $\endgroup$ – DanielWainfleet Apr 6 '18 at 22:27
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. I know this part. My main question is how to you keep track of elements and count them. For example how many A will be there in $S_n$ $\endgroup$ – Wiliam Apr 6 '18 at 13:05
  • $\begingroup$ That would involve solving a recurrence relation that, to my knowledge, isn't solvable. I imagine you could calculate the generating function, but you're probably out of luck regarding a closed form of $\#(S_n)$. $\endgroup$ – Austin Weaver Apr 6 '18 at 13:07
  • $\begingroup$ Right I see. What if the the original set is finite? I think that is also going to be numerically with brute force. $\endgroup$ – Wiliam Apr 6 '18 at 13:12
  • 1
    $\begingroup$ You should be able to easily calculate the sets' sizes using brute force and that recurrence. If the set not finite, then the size becomes $c$ after one or more iterations: $2^{\aleph_0} = c$ and $2^c = c$ $\endgroup$ – Austin Weaver Apr 6 '18 at 13:16
  • $\begingroup$ @Austin Weaver - I'm not an expert on infinite sets but en.wikipedia.org/wiki/Cantor%27s_theorem said any set is strictly smaller than its power set, so you cannot have $2^c = c$. $\endgroup$ – antkam Apr 6 '18 at 15:33
1
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.