3
$\begingroup$

Given a set M. Can I easily calculate the number of elements $S_i \in \mathcal{P}(\mathcal{P}(M))$ such that $\bigcup\limits_{s \in S_i}s = M$?

For example, $M = \{A,B\}$. Then the number of elements of $\mathcal{P}(\mathcal{P}(M))$ meeting that condition would be 10: there are $2^{2^2} = 16$ elements, every element except for $\emptyset, \{\emptyset\}, \{A\}, \{B\}, \{\emptyset, A\}, \{\emptyset, B\}$ has $A$ and $B$ in it.

Thanks in advance.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

A very nice question. You can determine this number using inclusion-exclusion. Denote $|M|$ by $n$, and consider the $n$ conditions of a particular element missing from the union. Then by inclusion-exclusion the desired count is

$$ \sum_{k=0}^n\binom nk(-1)^k2^{2^{n-k}}\;. $$

In your example with $n=2$, this is $2^{2^2}-2\cdot2^{2^1}+2^{2^0}=16-8+2=10$.

$\endgroup$
7
  • 1
    $\begingroup$ This is OEIS sequence A000371. $\endgroup$
    – joriki
    Apr 3, 2016 at 12:53
  • 1
    $\begingroup$ Wow thank you both very much. This was exactly what I was looking for. I'm pretty happy right now :) $\endgroup$
    – Alex
    Apr 3, 2016 at 13:05
  • $\begingroup$ To be honest, I don't really get it. For each $m \in M$, let $A_m$ denote the set of all $X \in \mathcal{P}(\mathcal{P}(X))$ such that $m \notin \bigcup X.$ Okay, now what? $\endgroup$
    – goblin GONE
    Apr 3, 2016 at 13:06
  • $\begingroup$ @goblin: That gives you the $k=1$ term: There are $\binom n1$ choices for $m$, and $|A_m|=2^{2^{n-1}}$ for all $m$. Then you need to do the same thing for any $B\subseteq M$ with $|B|=k$; there are $\binom nk$ choices of $B$, and $2^{2^{n-k}}$ elements of $\mathcal{P}(\mathcal{P}(X))$ whose union is disjoint from $B$. $\endgroup$
    – joriki
    Apr 3, 2016 at 13:10
  • $\begingroup$ @Alex: There were no "both"; I added the OEIS comment myself when it later occurred to me :-) I'm glad you're happy :-) $\endgroup$
    – joriki
    Apr 3, 2016 at 13:11

You must log in to answer this question.

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