# Permutations of binary set

Let $$S$$ be a binary multiset ($$\forall s \in S : s \in \{0, 1\}$$). Let $$x$$ be count of zeros in S and $$y$$ be the count of ones in $$S$$. Let $$A$$ be the ordered set of all permutations of $$S$$ sorted in lexicographic order $$A = \{\{00...0011...1\}, \{00...01011...1\}, \{00...01101...1\}, ...\}$$.

It can be seen that $$A$$ can be represented as a sorted set of natural numbers, if we assign a binary representation of some number to each permutation of zeros and ones.

So we have $$A = \{{a_1, a_2, a_3, ...}\}, \forall i \in N: {a_i} \lt {a_{i+1}} \$$ and there exists a bijective mapping between A and S.

Let $$f(x, y, n) = {a_n}$$

For example if $$S = \{0, 0, 0, 1, 1\}$$ then $$A = \{3, 5, 6, 9, 10, 12, 17, 18, 20, 24\}.$$

My goal is to find a formula for $$f(x, y, n)$$. Can you help me find such a formula?

P.S. I am also looking for articles on the topic of binary sets. I would be grateful if you share such articles.

• If you search OEIS for the example in your question you may find helpful information - for example oeis.org/A018900 , oeis.org/A294648 May 30, 2022 at 23:07
• It’s easier to think of $S$ as the subsets of $A$ as $x$-subsets of $\{1,2,\dots,x+y\}$ rather than permutations of a binary multisets May 30, 2022 at 23:16
• In other words, $f(x,y,n)$ is the $n$th largest number with $y$ ones and $\le x+y$ binary digits.
– anon
May 30, 2022 at 23:31