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**, IEEE Trans. Inf. Theory 19, 73-77 (1973). ZBL0247.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:

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