Permutations of binary set

214 Views Asked by At

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.