Computing the rank of a multiset after inserting another element
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) &amp;= \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) &amp;= 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$.