Considered a list sorted from A to Z containing all the permutations of the letters TIMEX, regardless if they form a real word or not. At what position will the word TIMEX appear?
1 - EIMTX
2 - EIMXT
3 - EITMX
...
? - TIMEX
?+1 - TIMXE
etc.
There are P(5) = 5! = 120 different permutations for the letters TIMEX. I thought that converting the letters to numbers might give me a clue on how to figure out the index.
E = 0
I = 1
M = 2
T = 3
X = 4
Therefore, TIMEX spells 31204.
I could obviously count all permutations by holding the first letters constant: 0XXXX = P(4) = 24
1XXXX = P(4) = 24
2XXXX = P(4) = 24
30XXX = P(3) = 6
310XX = P(2) = 2
31204 = P(1) = 1
Total: 81th position.
But is there a faster way? Like converting 31204 (5-digits system) to 3*5^4 + 1*5³ + 2*5² + 0*5¹ + 4 = 2054 (decimal sistem).
Does this number tell me anything useful?
The way this works is by finding each initial letter from the remaining permutations, so first we find:
$ 0xxxx\;(24)\\ 1xxxx\;(24)\\ 2xxxx\;(24)\\ 3xxxx $
which, using a $1$-based counting system, places us at the $3\times24+1=73^{rd}$ position, and we continue using the fact that the remaining elements are $\{0,1,2,4\}$ and we want element $1$ which is in the $1^{st}$ position of the remainder set (using a $0$-based counting system), so next we find:
$ 30xxx\;(6)\\ 31xxx\;(6) $
which takes us to the $73+6+6=85^{th}$ position.
Continuing we get to:
$ 310xx\;(2)\\ 312xx\;(2) $
so position $85+2+2=89^{th}$ and this is the final position, as the final remainder set is $\{0,4\}$.
We can use the factorial base:
$$p_0\times(n-1)! + p_1\times(n-2)!+\dots+p_i\times(n-i-1)!+\dots+0!$$
where $p_i$ represents the position of the $i^{th}$ element in the remainder set of after each iteration.
We can see this from considering (in normal permutations) $54321$, which gives the position of this as:
$$4.4!+3.3!+2.2!+1.1!+0!=96+18+4+1+1=120$$