4
$\begingroup$

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$?

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.