My goal is to determine the lexicographic index of an $M$-ary $n$-sequence $\mathbf{x}$ on the subset with an $M$-weight sum constraint:
$$S = \{ \mathbf{x} \in \{0, \ldots, M-1\}^n: \sum\_{j=1}^n x\_j = M-1 \}$$


Is there a formula for this index? That is, I would like an expression for $i\_S(\mathbf{x})$ explicitly in terms of sums of binomial coefficients that are functions of $\mathbf{x}$, $n$, $M$ and sum indices.


This is a combination of Proposition 2 and Example 2 of the following paper, if it helps: *Cover, Thomas M.*, [**Enumerative source encoding**](http://dx.doi.org/10.1109/TIT.1973.1054929), IEEE Trans. Inf. Theory 19, 73-77 (1973). [ZBL0247.94009](https://zbmath.org/?q=an:0247.94009).


Example of desired input $\to$ output:


$(0, 0, \ldots,0, M-1) \to \text{index } 0 $


$(0, 0, \ldots,1, M-2) \to \text{index } 1$


$\ldots$


$(M-1, 0, \ldots, 0) \to \text{index } {n+M-1\choose n-1}$


Notes from the Cover reference:


1. Let $n\_s(x\_1, \ldots, x\_k)$ denote the number of elements in $S$ for which the first $k$ co-ordinates are given by $(x\_1, \ldots, x\_k)$.
2. When the weight constraint doesn't exist, then the index is given by:
$$i\_s(\mathbf{x}) = \sum\_{j=1}^n \sum\_{m=1}^{x\_j-1} n\_s(x\_1, x\_2, \ldots, x\_{j-1}, m)$$
3. For binary partitions ($\mathbf{x}\in\{0,1\}^n$) with weight $w$:
$$n\_s(x\_1, x\_2, \ldots, x\_{j-1}, 0) = {n-j \choose w'(w,j)}$$
Here, $w'(w,j) = w - \sum\_{k=1}^{j-1} x\_k$. This gives us:
$$i\_s(\mathbf{x}) = \sum\_{j=1}^n x\_j {n-j \choose w'(w, j)}$$


Combining the previous two results would give me the result I need. Is it straightforward to do so?


BONUS (optional): In addition, is it possible to invert the index to its corresponding partition easily?


I did find similar posts about lexicographic partition indexing but they didn't have any concrete answers. 



Source coding lexicographic index of finite alphabet sequence with weight (partitions)
I was able to put the information from the two propositions in the paper together to get an explicit expression. The index should be:
$$i\_S (\mathbf {x})=\sum\_{k=1}^n \sum\_{j=1}^{x\_k-1} n\_S (x\_1, \ldots,x\_{k-1},j)$$
And further:
$$n\_S (x\_1, \ldots,x\_{k-1},j)={{n-\sum\_{l=1}^{k-1} x\_l -j +m -k-1} \choose {m-k-1}}$$
Explanation:
$n\_S (x\_1, \ldots,x\_{k-1},j)$ counts how many ways the available remaining $c=n-\sum\_{l=1}^{k-1} x\_l -j$ units can be distributed among the remaining $b=m-k$ positions, when the first $k-1$ positions have been populated and the $k$th position has $j$ units in it. 


This is equivalent to distributing $c$ identical balls among $b$ different boxes.


(TODO: cleanup typos)


