# Formulas for mappings between power set $P_n$ and $1, \ldots, 2^n$

Let $A_n$ be the ordered set of integers from $1$ to $n$ $$A_n = \left\{1, 2, 3, \ldots, n-2, n-1, n \right\},$$ let $B_n$ be the ordered set of integers from $1$ to $2^n$ $$B_n = \left\{1, 2, 3, \ldots, 2^n -2, 2^n -1, 2^n \right\},$$

and let $P_n$ be the power set of $A_n$ with elements ordered linearly by size and then lexicographicly within each size, that is \begin{align} P_n = & \left\{\emptyset,\right. \{1\}, \{2\}, \ldots, \{n-1\}, \{n\}, \\ & \{1, 2\}, \{1, 3\}, \ldots, \{1, n-1\}, \{1, n\},\\ & \{2, 3\}, \{2, 4\}, \ldots, \{2, n-1\}, \{2, n\},\\ & \ldots, \\ & \{1, 2, 3\}, \{1, 2, 4\}, \ldots, \{1,2, n-1\}, \{1, 2, n\},\\ & \{1, 3, 4\}, \{1, 3, 5\}, \ldots, \{1,3, n-1\}, \{1, 3, n\},\\ & \ldots\\ & \{1, 2, \ldots, n-2, n-1\}, \{1, 2, \ldots, n-2, n\}, \ldots, \{2, 3, \ldots, n-1, n\},\\ & \left. \{1, 2, \ldots, n-1, n\} \right\}. \end{align} The set $P_n$ has $2^n$ elements.

What are the bijective functions/formulas $f:B_n \to P_n$ and $g:P_n \to B_n$ that map the elements of the sets $B_n$ and $P_n$ by keeping the order constant, that is the image by $f$ of the $k$th element of $B_n$ is $k$th element of $P_n$, and likewise for $g$?

Unfortunately, an algorithm that needs to enumerate the elements of $P_n$ is not an option here. However, a collection of bijective function $f_0, f_1, \ldots, f_{n-1}, f_n$ and/or $g_0, g_1, \ldots, g_{n-1}, g_n$, where $f_k$ and $g_k$ denote functions that do the mapping for sets of $P_n$ of size $k$ could be an option.

Note: This question has similarities with that question. However, the answers there are not helpful directly for this question, at least I couldn't figure out how.
The answer by @DonAntonio enumerates the elements of $P_n$ but leaves it to the reader to actually find the function/formula for the mapping.
The answer by @MJD is based on a different ordering of the elements of $P_n$ (maybe a maping between "his" ordering and "my" ordering might help), and it doesn't seem provide the function requested here.

-
Your description of $f$ and $g$ is vague. Dots are used to abbreviate notation, where there is a obvious pattern. I don't think, it is obvious here. – Tomas Jul 18 '13 at 19:31
@Tomas, I've edited the question to hopefully remove any doubt. – QuantIbex Jul 18 '13 at 21:57

For $S\subseteq A_n$ let

$$g(S)=1+\sum_{k\in S}2^{k-1}\;.$$

The inverse function $f:\{1,\ldots,2^n\}\to\wp(A_n)$ can then be calculated as follows. To find $f(k)$, first write $k-1$ in binary as $b_nb_{n-1}\dots b_2b_1$; then $f(k)=\{i:b_i=1\}$.

-
If I understand this correctly, these functions don't provide the desired result because they rely on a different ordering of the elements of $P_n$. For example, $S = \left\{1, 2\right\}$ is the $(n+2)$th element of $P_n$, so $g(S)$ should be the $(n+2)$th element of $B_n$, that is $n+2$, but here $g(S)=4$. And, if $k = 4$, which is the $4$th element of $B_n$, $f(k)$ should be the $4$th element of $P_n$, that is $\{3\}$, but here $f(k)=\{1, 2\}$. The requested functions need to map the $k$th element of $B_n$ with the $k$th element of $P_n$. – QuantIbex Jul 19 '13 at 10:24

The $N$th power set is given by the binary representation of $N$. So assume for the sake of argument that the binary representation is given by a left zero padded vector of dimension $M: B=(0,0,0,\ldots, 1,\ldots, 0,\ldots)$, we then have the vector in $M$-dimensions representing the set: $X=(x_0, x_1, x_2, \ldots, x_M)$.

This yields that the power set has a representation: $$P_i = X B_i,$$ assuming without loss of generality that $X_i \geq 1$ and $0=\emptyset$.

-
I've edited your answer, marking mathematical expressions with $\TeX$. Could you please check that it still corresponds to what you meant? – QuantIbex Jul 18 '13 at 22:04