# Mapping permutations of multisets to integers

Is there an inversible way to map the permutations of a multiset to integers such that no values are omitted?

In particular I'm interested in mapping a binary number of size n, that consists of exactly two 1s to integers, but out of curiosity I'd like to know if there is a general way to do this.

To illustrate my problem consider the multiset {0,0,1,1}, then a possible mapping would be:

0: {0,0,1,1}
1: {0,1,0,1}
2: {0,1,1,0}
3: {1,0,0,1}
4: {1,0,1,0}
5: {1,1,0,0}

• This might be relevant. – Jens Oct 27 '17 at 2:38

You want a bijection between the $N = n(n-1)/2$ two element subsets of $\{1, \ldots, n\}$ and the integral range $\{1, \ldots, N\}$;

The clue to finding one is to think about the proof without words that finds the triangular numbers.

Think of the two element subsets as the pairs $(x,y)$ with $x > y$. Then number the corresponding lattice points this way:

            * 11
*  7 12
*  4  8 13
*  2  5  9 14
*  1  3  6 10 15


where the *s are on the diagonal $x=y$.

Then $(x,y)$ is numbered $$\frac{x(x+1)}{2} -y .$$

The inverse of this bijection is a little harder to calculate.

You could map the string with $1$ in positions $a$ and $b$ (zero based) to $an + b$. That gives you a range for the $n(n-1)/2$ values of $[n+1, \ldots, n^2 -2 ]$ instead of the obvious $[0, \ldots, 2^n -1 ]$ which has many more omitted values.

• Is there a way to do this without gaps? I've edited the question to make my problem more clear. – G.G Oct 27 '17 at 0:13
• I'll think about "no gaps" in the morning ... – Ethan Bolker Oct 27 '17 at 0:26