0
$\begingroup$

The question is: How many curly brackets are there in the following, if $\varnothing$ counts as $\{ \}$ (=1 curly brackets)

$$ \wp^5(\varnothing) $$

I calculated $p^2$, which was $4$ curly brackets, but at $p^3$: $$ \wp^3(\varnothing) $$

I found out it has 8 curly brackets (still have to double check). But I'm really confused at how I can calculate this till the power of 5.

Thank you!

$\endgroup$
  • $\begingroup$ Try to calculate $\mathcal{P}^4(\emptyset)$. It might be a bit tiring, but you should start to see a pattern emerge. $\endgroup$ – EuYu Jun 20 '14 at 23:33
  • $\begingroup$ $\pe$ is the Weierstrauss elliptic function, $\mathcal{P}$ is the power set. $\endgroup$ – Rene Schipperus Jun 20 '14 at 23:33
  • 1
    $\begingroup$ I wrote out $\mathcal{P}^{3}(\emptyset)$ and got $11$ pairs of curly brackets. You might want to double check that. $\endgroup$ – JimmyK4542 Jun 21 '14 at 0:21
  • 1
    $\begingroup$ @Rene: I have seen from time to time that some people use $\wp$ for the power set. (The code is \wp by the way.) $\endgroup$ – Asaf Karagila Jun 21 '14 at 0:39
  • $\begingroup$ Yeah I was trying to change it when the site went down. I think $\wp$ should be reserved for the elliptic function and a different symbol for power set should be used. $\endgroup$ – Rene Schipperus Jun 21 '14 at 0:56
2
$\begingroup$

Let $b_n$ be the number of elements in $\mathcal{P}^{n}(\emptyset)$. Let $a_n$ be the number of curly brackets in $\mathcal{P}^{n}(\emptyset)$.

Clearly, $b_n = 2^{b_{n-1}}$. Therefore, $b_0 = 0$, $b_1 = 1$, $b_2 = 2$, $b_3 = 4$, $b_4 = 16$, and $b_5 = 65536$.

Each element of $\mathcal{P}^{n-1}(\emptyset)$ will be in half of the subsets of $\mathcal{P}^{n-1}(\emptyset)$, i.e. half of the elements of $\mathcal{P}^{n}(\emptyset)$. Thus, each element of $\mathcal{P}^{n-1}(\emptyset)$ gets written down $\tfrac{b_n}{2}$ times in $\mathcal{P}^{n}(\emptyset)$.

This requires a total of $\tfrac{b_n}{2}(a_{n-1}-1)$ pairs of curly brackets.

Then, we need one pair of curly brackets for each element of $\mathcal{P}^{n}(\emptyset)$, (so $b_n$ of them), as well as one more pair for the outermost curly brackets in $\mathcal{P}^{n}(\emptyset)$.

Therefore, this is a total of $a_{n} = \tfrac{b_n}{2}(a_{n-1}-1) + b_n + 1 = \tfrac{b_n}{2}(a_{n-1}+1)+1$ curly brackets.

Now, crank out the recursion to get: $a_0 = 1$, $a_1 = 2$, $a_2 = 4$, $a_3 = 11$, $a_4 = 97$, $a_5 = 3211265$.

So, we need $3211265$ pairs of curly brackets to write out $\mathcal{P}^{5}(\emptyset)$.

$\endgroup$
  • $\begingroup$ Thank you! I really spent 1 hour studying your answer and just got a eureka moment and understand it myself. Thank you! $\endgroup$ – user3125591 Jun 21 '14 at 12:26

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.