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$
3
  • $\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
    Commented Apr 6, 2018 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
    Commented Apr 6, 2018 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$ Commented Apr 6, 2018 at 22:27

2 Answers 2

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.

$\endgroup$
6
  • $\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
    Commented Apr 6, 2018 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$ Commented Apr 6, 2018 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
    Commented Apr 6, 2018 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$ Commented Apr 6, 2018 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
    Commented Apr 6, 2018 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.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .