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


The [multiset](http://mathworld.wolfram.com/Multiset.html) $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$?



Is there a function that determines the rank of a multiset after inserting another element?
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)$. 


