I have the following problem:
Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists of all permutations of $x$. We call this set the type class of $x$.
My question:
How to compute the position of $x$ in the lexicographical ordering of $S$?
I found the paper "Enumerative source coding" written by Thomas M. Cover, where this position function $i_{S}$ is shown for binary alphabets (in the following the alphabet is $\{0,1\}$):
$i_S(x_1x_2\cdots x_n)=\sum\limits_{k=1}^{n}x_k\cdot$ $n-k\choose n(w,k)$
with $\;\;n(w,k)=w-\sum\limits_{j=1}^{k-1}x_j\;\;\;$
and $\;\;w$ is the number of occurrences of $1$ in $x\;\;$ ($w=\sum\limits_{k=1}^{n}x_k$).
Unfortunately, i do not know how to extend this formula to alphabets of size $M$. Any help?