## Is there a function that determines the rank of a multiset after inserting another element?

For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements.

The multiset $M = (1,1)$ has rank $5$ because there are $4$ multisets less than it based on lexicographic ordering: $(0), (1), (0,0), (0,1)$.

If we insert $0$, we get $(0,1,1)$ which has rank $8$. If $1$ were inserted instead we'd have $(1,1,1)$ with rank $9$.

Is there a function $f(r,x,n)$ which takes a multiset rank $r$, an element $x$, and $n$, and returns the new rank after inserting $x$?

-
 It is not clear that rank is unique. What if the set has rank 87 because it contains the number 53? Gerhard "Ask Me About System Design" Paseman, 2012.10.26 – Gerhard Paseman Oct 27 at 1:58 What is the definition of rank? What's the numerical ordering? – Will Sawin Oct 27 at 2:24 here is one definition: math.stackexchange.com/questions/167513/… – tilbren Oct 27 at 2:32

Start by attempting the problem for ordered multisets; once you have found a formula, go back and adjust for non-ordered multisets (if you so desire).

First, re-stating your ranks for ordered multisets: The rank of (1,1) is 6, since it's what you have and (1,0). Similarly, (0,1,1)'s rank is 10, because it has 9 multisets less than it (omitting parentheses and commas): 0, 1, 00, 01, 10, 11, 000, 001, 010.

Next: to find the rank of a lexicographically ordered multiset, concatenate the elements with an extra 1 at the start, view this as a binary number, and subtract 1 from its decimal representation. For example, (1,1) becomes 111 which is binary for 7. Now subtract 1 to get rank 6. Similarly, (0,1,1) becomes 1011 which is binary for 11. Subtract 1 to get rank 10.

I am quite certain the above is sufficient for you to work out $f(2,x,n)$ and - though slightly more difficult - to work out $f(3,x,n)$, after which you can probably figure out $f(r,x,n)$.

-
 Thanks for the awesome solution! – tilbren Oct 27 at 3:38 It's far from a full solution, but it should be enough for you to derive the answer yourself (and I hope you'll post it here if/when you do!). – Benjamin Dickman Oct 27 at 4:01