|
The factorial based radix or factoradic is a factorial based mixed radix numeral scheme:
radix: 5! 4! 3! 2! 1!
decimal: 120 24 6 2 1
In this numbering system, the rightmost digit may be 0 or 1,
the next 0, 1, or 2, and so on. The numbers from 0 to 24 are
decimal factoradic
0 0
1 1
2 10
3 11
4 20
5 21
6 100
7 101
8 110
9 111
10 120
11 121
12 200
13 201
14 210
15 211
16 220
17 221
18 300
19 301
20 310
21 311
22 320
23 321
24 1000
For another example, the biggest number that could be represented with five digits would be 54321 which equals 719 in decimal:
- 5×5!+4×4!+3×3!+2×2!+1×1!.
It might not be clear at first sight but factorial based numbering system is also unambiguous. No number can be represented by more than one way because the sum of respective factorials multiplied by the index is always the next factorial minus one:
- <math> \sum_{i=1}^{n} {i.i!} = {(n+1)!} - 1. <math>
This can be easily proved with mathematical induction.
There is a natural mapping between the integers 1 .. n! (or equivalently
the factoradic numbers with (n-1) digits) and permutations of n elements in lexicographic order, when the integers are expressed in factoradic form. For example, with n=3, such a mapping is
decimal factoradic permutation
0 00 (0,1,2)
1 01 (0,2,1)
2 10 (1,0,2)
3 11 (2,0,1)
4 20 (1,2,0)
5 21 (2,1,0)
where the leftmost factoradic digit (0..2) specifies the
placement of the 0 in the permutation, the rightmost
digit (0..1) specifies the placement of the 1 in the
remaining two possible locations, and the 2 is put in
the last open location in the permutation list.
A similar concept, combinadics, can be used to find combinations.
|
