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.

  • $\begingroup$ If you search OEIS for the example in your question you may find helpful information - for example oeis.org/A018900 , oeis.org/A294648 $\endgroup$ May 30, 2022 at 23:07
  • $\begingroup$ 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 $\endgroup$ May 30, 2022 at 23:16
  • $\begingroup$ In other words, $f(x,y,n)$ is the $n$th largest number with $y$ ones and $\le x+y$ binary digits. $\endgroup$
    – anon
    May 30, 2022 at 23:31


You must log in to answer this question.

Browse other questions tagged .