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](http://en.wikipedia.org/wiki/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 .



Indexing combinations with repetition
@PietroMajer's comment essentially contained the answer already:


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.


