Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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\}$.

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.