Combinatorics – Direct Formula for Elements of Power Set

combinatoricselementary-set-theory

Let $A_n$ be an ordered set: $$A_n = \{ 1,2,3,\dots,n\}$$ Then the powerset of $A_n$ lets call it $P_n$, is $$P_n=\{\emptyset,\{1\},\{2\},\dots,\{1,2\},\{1,3\},\dots,\{1,2,3,\dots,n\}\}$$

How can I find the formula $F(i,j)\colon\mathbb{N}\times\mathbb{N} \to \mathbb{N}$, that given $i$ and $j$ will return $P_n[i][j]$, that is $j$'th element in $i$'th set of $P_n$?
I searched google but couldn't find anything like that.

Edit: How about a formula that returns the number of elements in $i$'th set in powerset?

Best Answer

The easy thing to do is to notice that the $2^n$ subsets of an $n$-element set correspond in a natural way to the binary expansions of the numbers $0\ldots 2^n-1$:

000 {     }
001 {    a}
010 {  b  }
011 {  b,a}
100 {c    }
101 {c,  a}
110 {c,b  }
111 {c,b,a}

If you're willing to order the sets in this way, then the $n$th set contains element $m$ exactly when the binary expansion of the number $n$ has its $m$th-least significant bit set.

Let's write $f_m(n)$ for the function that has value 1 if the $m$th bit of the binary numeral $n$ is a 1, and 0 if it is a 0; it has value 1 if the $n$th subset contains the $m$th element, and 0 if not. Then $f_0(n) = n\bmod 2$, and

$$ \begin{align} f_m(n) & = f_{m-1}\left(\left\lfloor \frac n2\right\rfloor\right) \\ & = f_{0}\left(\left\lfloor \frac n{2^m}\right\rfloor\right) \\ & = \begin{cases}1,&\text{if $\left\lfloor \frac n{2^m}\right\rfloor$ is odd}\\0,&\text{if it is even}\end{cases} \end{align} $$

Related Question