Computing the rank of a multiset after inserting another element

Question

What is the procedure for computing the rank of a multiset after inserting an 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 rank $r$, an element $x$, and $n$, and returns the new rank after inserting $x$?

Answer 1

I'll consider the easy $|S|=2$ case. There are $n+1$ multisets of size $n$, and so the rank of the multiset $0^{n-k} 1^k$ is $$ r(n,k) = \sum_{m=0}^{n-1} (m+1) + k = \frac{n(n+1)}{2} + k. $$ What happens when adding an element? Adding $0$ and $1$, respectively, correspond to $r(n+1,k)$ and $r(n+1,k+1)$. We have $$ \begin{align*} r(n+1,k) &= \frac{(n+1)(n+2)}{2} + k = n + 1 + \frac{n(n+1)}{2} + k = n+1 + r(n,k), \\ r(n+1,k+1) &= r(n+1,k)+1 = n+1 + r(n,k) + 1. \end{align*} $$ Therefore the function you want is $$ f(r,x,n) = r + n+1 + x. $$ Here $n$ is the size of the old multiset, rather than the number of elements. For example, the rank of $(1,1)$ is $5$, and $f(5,0,2) = 5 + 3 + 0 = 8$, $f(5,1,2) = 5 + 3 + 1 = 9$.