There are 6!=720 permutations of {1,2,3,4,5,6}. Using Lehmer codes each permutation has a lexicographic index.
There are 6!/(3! 3!)=20 permutations of {0,0,0,1,1,1}. Is there a way to index these in a way similar to the lexicographic index? Is there some sort of system related to simplex coordinates?
Of the binary numbers up to $2^{100}-1$, exactly ${100}\choose{7}$ =16007560800 of them have exactly seven 1's. Which of these numbers has index 8000000000?
Does it help that there are exactly as many 8-part integer partitions of 101?
Total[(Multinomial @@ Tally[#][[All, 2]]) & /@ IntegerPartitions[101, {8}]]
The integer partitions before {32,21,16,11,10,7,3,1} are 6416 short of 8000000000, so I suppose taking the 6416th permutation of that would give the gaps between the ones in one indexing system. But is there a more elegant way?
Best Answer
You can clasify these sort of structures using pascal's triangle (recursively) . We have $C^{a}_{b} = C^{a-1}_{b} + C^{a-1}_{b-1}$ . Every number $n$ from $1$ to $C^{a}_{b}$ can be decomposed as: $$n = \sum_{t=b..s} C^{k_t}_{t}$$ with $k_s = s$ and $k_t > k_{t-1}$ and $s \leq b$ . This would correspond to the digit sequence where the digits indexed by $k_t + 1, t\neq s$, and the first $s$ digits would be $1$ and the rest would be $0$. The ordering would be in terms of increasing binary numbers (natural ordering). Let's apply this to $8000000000$ and ${100}\choose{7}$. $$8000000000 = {{90}\choose{7}} + {{87}\choose{6}} +{{79}\choose{5}} + {{73}\choose{4}} + {{47}\choose{3}} + {{42}\choose{2}} + {{40}\choose{1}} + {{0}\choose{0}}$$ Note that ${{0}\choose{0}}$ is here defined as $0$ in order to maintain the recurrence relation. In conclusion, corresponding to the 8000000000 index would be the binary number who's $1$ digits are indexed by $\{91,88,80,74,48,43,41\}$. When decomposing the number into a sum of combinations, we must always choose the maximum $k_t$ of $C^{k_t}_{t}$ such that the remainder is positive (excluding the case where $t=1$ or $k_t = t$, when we will have remainder 0) . Eg: $2 = {{7}\choose{7}} + {{6}\choose{6}}$ means the 8'th digit and the first 6 digits will be $0$, giving 10111111.
Edit: adding answer to " What year does this date back to? Is there a multinomial version for permutations of $\{0,0,1,1,2,2,2\}$?"
I'm sure someone's used this algorithm before, but I've just made it up on the fly. I couldn't find any reference. If you can order and count something, you can index it. I will do a rough outline of the algorithm for $\{0,0,1,1,2,2,2\}$
Let's take again the natural order in base "3". There's a total of $\frac{7!}{3!2!2!} = 210$ numbers formed by permuting the digits $\{0,0,1,1,2,2,2\}$ . Let's say we're given a random index $0<n\leq 210$ and our aim is to construct the corresponding number. First we determine what is the $7$'th digit of our number (counted right to left, aka. the $7$'th digit is the left-most digit), as there are a total of 7 digits. It can be either $0$,$1$, or $2$. The $7$'th digit is the most significant for our ordering.
Numbers with the $7$'th digit $0$ are smaller than numbers with $7$'th digit $1$ are smaller than numbers with $7$'th digit $2$ (we have $0...$ < $1...$ < $2...$ ). So those ending with $0$ are counted first, followed by those with $1$, followed by those with $2$. There are $\frac{6!}{3!2!1!} = 60$ numbers with $7$'th digit $0$, $\frac{6!}{3!1!2!} = 60$ numbers with $7$'th digit $1$ and $\frac{6!}{2!2!2!} = 90$ numbers with $7$'th digit $2$. A total of $210$ numbers. Arranged ascendantly, this splits $(0,210]$ in $\{(0,60],60 + (0,60],60+60 + (0,90]\} =\{(0,60], (60,120], (120,210]\}$. These are the intervals of the indices of the numbers who's $7$'th digit is $0$, $1$ and $2$. We find out to which one of these intervals $(a,k+a]$ does our $n$ belong to, make a note the corresponding $7$'th digit, then "forget" it: we do this by considering the remaining six digits as being indexed by $n-a$, from $(0,k]$ and applying the formula recursively for these remaining $6$ digits.