3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there a mathematical question here somewhere? I don't understand your initial question "Is there a formula for this index?" What index? Also what do you mean by "rank" and what does the $\equiv$ notation mean in this context? One more thing, $(0,0,\dots,0,M-1)$ is not contained in $S$. Neither is $(0,0,\dots,1,M-2)$ or $(M-1,0,0,\dots,0)$. $\endgroup$ – Jon Noel Jul 7 '17 at 22:03
  • $\begingroup$ I have edited the question to make it clearer and fixed some typos. I had used 'rank' and 'index' interchangeably and redundantly; I use only 'index' now to mean 'lexicographic index'. $\endgroup$ – Salmonstrikes Jul 8 '17 at 2:14
0
$\begingroup$

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)

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