Source coding lexicographic index of finite alphabet sequence with weight (partitions)

Question

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:

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.

Answer 1

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)