# Indexing combinations with repetition

Let $$\Sigma$$ be a finite set of symbols with total order. Let $$C_k$$ be the set of all $$k$$-multiset (unordered collection of $$k$$ elements from $$S$$, with repetition allowed). We can order all the elements of $$C_k$$ in lexicographic order and index each element in that order i.e a bijective function $$f: C_k \to [ 1, |C_k| ]$$ can be defined where $$f(x)$$ will be the position/rank of $$x$$ in such ordering (Here $$|C_k| = \binom{k + |\Sigma| -1}{|\Sigma|-1})$$. I am looking for such bijective function which can be computed for any $$x \in C_k$$ without having sort the elements or to refer to any other element of $$C_k$$ in any way. Can we build such function?

UPDATE: When repetition is not allowed, i.e. indexing $$k$$-subsets of a set is solved as follows: arrange $$k$$ elements in decreasing order. Let such an ordering be $$c= c_k, ..., c_1$$ ($$c_k > c_{k-1}>...> c_1$$), then $$f(c) = \sum_{i = 1}^{k} \binom{c_i}{i}$$ gives such a bijection. (Combinatorial Number System)

ADDITION: My original question is answered. This gives lexicographical ordering when k-combinations are taken as decreasing sequence. How do we define a function which gives ordering as that of lexicographic order when k-combinations are taken as increasing. Mind that these two ordering are not 'reverse' of each others. Eg. When $$S=\{0,1,2,3\}$$ and we want ordering of 2-sets then the increasing ordering would give the ordering as: 01, 02,03, 12, 13, 23; and the decreasing ordering would give then ordering as: 01, 02, 12, 03, 13, 23 .

• Just consider $C_k\ni a\mapsto f(a_k+k-1, a_{k-1}+k-2, \dots,a_2+1,a_1)$ (where the $a_j$'s are arranged in decreasing order, $a_k\ge a_{k-1}\dots\ge a_1$). – Pietro Majer Oct 9 '13 at 19:46
• @PietroMajer. I have added another sub-question, in cases where k-sets are ordered in increasing lexicographic order. – DurgaDatta Oct 10 '13 at 12:26
• As to the new question: the two order relations are not reverse of of each other, true; yet they are isomorphic. – Pietro Majer Oct 10 '13 at 12:28
• Correct. Now, my intent is not just indexing but also preserve the order. I am using these index where order is important. – DurgaDatta Oct 10 '13 at 12:29
• I'm saying there is again simple order isomorphism. Precisely, between what you call the "increasing ordering" and the "reversed decreasing ordering". Take an increasing sequence $(a_i)$ to $(k-a_{k-i+1})$. E.g. $01, 02, 03, 12, 13, 23$ are mapped resp. to $23, 13, 03, 12, 02, 01$; then apply the previous $f$ valued in $\{1,2,3,4,5,6\}$ followed by $x\mapsto 7-x$. – Pietro Majer Oct 10 '13 at 12:53

Define a bijection $\phi$ between $k$-multisubsets of $\{ 1,\ldots,n \}$ to $k$-subsets of $\{ 1,\ldots,n+k-1\}$ by sending $\{ c_0 \leq c_1 \leq \ldots \leq c_{k-1} \}$ to $\{ c_0 < c_1+1 < c_2 + 2 < \ldots < c_{k-1}+k-1 \}$.
This map sends lex order on the $k$-multisubsets to lex order on $k$-subsets. Thus, given your lex-position map $f$ on $k$-subsets provides the lex-position map $f \circ \phi$ on $k$-multisubsets.
• ya, I was mistaken. I have added another sub-question (increasing k-sets). How do we modify $f$ now? – DurgaDatta Oct 10 '13 at 12:18
• What about this: take the $i$-th word in your increasing ordering, reverse it, and add it to the $i$-th last word in your decreasing ordering. What you get is always get $(3,3)$. Is this a coincidence, or might it give you a way of producing the order? – Christian Stump Oct 10 '13 at 12:54