Direct formula for elements of power set?

Question

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?

Answer 1

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} $$

Answer 2

First, I supose we'd have to define a definite order in $\,P_n:=P(A_n)\,$ , and for this we could do something ressembling the cycles in the permutations group $\,S_n\,$ (if you still haven't studied this don't worry: you won't need it but perhaps it will help others to feel more comfortable with the following), so we can try the lexicographic order.

First, we agree to "order" the elements within each element in $\,P_n\,$ (i.e., within each subset of $\,A_n\,$) in ascending natural order, so that we'll write $\,\{3,5,6,9\}\,$ and not $\,\{5,9,3,6\}\,$ or $\,\{3,6,5,9\}\,$ , etc.

Take now $\,A,B\in P_n\,,\,A=\{i_1,...,i_r\}\,,\,B=\{j_1,...,j_s\}\,,\,\,i_k,j_m\in A_n\,,\,1\leq r,s,\leq n\,\,$ , and define

$$A\prec B\Longleftrightarrow \begin{cases}|A|<|B|\;\;,\text{ or}\\r=s\,\,\wedge\,\,\exists\, 1<k<r\,\,\;s.t.\;\,\,i_1=j_1\,,\,...,i_k=j_k\,,\,i_{k+1}<j_{k+1} \end{cases}$$

Thus, for example, $\,\{6,7,9\}\prec\{1,2,3,4,\}\,\,,\,\,\{4,7,9\}\prec\{4,7,11\} \,$ , etc.

With the above order we can ennumerate the elements of $\,P_n\,$ , beginning from zero to include the empty set:

$$0\to\emptyset\\1\to\{1\}\\...\\n\to\{n\}\\n+1\to\{1,2\}\\n+2\to\{1,3\}\\...\\n+n-1=2n-1\to\{1,n\}\\...$$

The resulting matching is not the nicest thing one could expect to meet in the street, but it is also not that terrible. Now you can define your function, perhaps first trying some easy examples when $\,n=3,4,5\,$...have fun!