Factorial decomposition of integers?

This question might seem strange, but I had the feeling it's possible to decompose in a unique way a number as follows:

if $x < n!$, then there is a unique way to write x as: $$x = a_1\cdot 1! + a_2\cdot 2! + a_3\cdot3! + ... + a_{n-1}\cdot(n-1)!$$ where $a_i \leq i$

I looked at factorial decomposition on google but I cannot find any name for such a decomposition.

example:

If I chose :

(a1,a2) =

• 1,0 -> 1
• 0,1 -> 2
• 1,1 -> 3
• 0,2 -> 4
• 1,2 -> 5

I get all number from $1$ to $3!-1$

ideas for a proof:

The number of elements between $1$ and $N!-1$ is equal to $N!-1$ and I have the feeling they are all different, so this decomposition should be right. But I didn't prove it properly.

Are there proofs of this decomposition? Does this decomposition as a name? And above all is this true ?

• It's true, and the proof is easy by induction on $n$. What have you written down? – Olivier Bégassat Jul 23 '11 at 9:19
• I am not sure about number-theory tag, if someone has a better idea, please retag the question. – Martin Sleziak Jul 23 '11 at 9:21
• @Olivier, I actually thinking of a mapping between n! and all permutation, and I should have used that as a proof. But since I couldn't find anything on the web about that I had the feeling something was wrong ... :D! – Ricky Bobby Jul 23 '11 at 9:28
• @Martin: Possibly combinatorics? – Brian M. Scott Jul 23 '11 at 9:39
• If any of you have a good reason to think (number-systems) doesn't belong, please remove that tag... – J. M. is a poor mathematician Jul 23 '11 at 11:56

You're looking for the factorial number system, also known as "factoradic". Searching should give you more results.

Yes, it's true that such a decomposition is always possible. One way to prove it is as follows: given $x < n!$, consider the $x$th permutation of some ordered set of $n$ symbols. This is some permutation $(s_1, s_2, \dots, s_n)$. Now for $s_1$ you had $n$ choices (label them $0$ to $n-1$) and you picked one, so let $a_{n-1}$ be the choice you made. For $s_2$ you had $n-1$ choices (label them $0$ to $n-2$) and you picked one, so let $a_{n-2}$ be the number of the choice you made. Etc. $a_0$ is always $0$ because you have only one choice for the last element. (This is also known as the Lehmer code.)

• I was actually thinking about permutation when this question came to my mind, I didn't thought about using it to prove the decomposition. thanks a lot for your answer. – Ricky Bobby Jul 23 '11 at 9:17
• Why not try what would seem obvious? Divide your numberx by n!, take the highest multiplr $a_n$ with $a_nn!<x$, then divide the remainder x-$a_n n!$ by (n-1)! and take $a_{n-2}$ as the largest multiple, etc. at the end, you will be left with some amount which is always a multiple of 1=1! – gary Jul 23 '11 at 9:37
• @gary: Yes, something like that would work too, if done correctly. But for me, this map numbering permutations was actually more obvious. :-) (You want to divide by $(n-1)$ the first time, also you need to prove that $a_i \le i$ for all $i$. This is easy, but it's not just one line.) – ShreevatsaR Jul 23 '11 at 9:46
• Shreevatsa: if your coefficient for n! was larger than n, then n(n-1)!=n! , and you could then increase your previous coefficient for n! by (at least )1. But alternative explanations are always useful,helpful. – gary Jul 23 '11 at 10:12

Your conjecture is correct. There is a straightforward proof by induction that such a decomposition always exists. Suppose that every positive integer less than $n!$ can be written in the form $\sum_{k=1}^{n-1} a_k k!$, where $0 \le a_k \le k$, and let $m$ be a positive integer such that $n! \le m < (n+1)!$. There are unique integers $a_n$ and $r$ such that $m = a_nn! + r$ and $0 \le r < n!$, and since $m < (n+1)! = (n+1)n!$, it’s clear that $a_n \le n$. Since $r < n!$, the induction hypothesis ensures that there are non-negative integers $a_1,\dots,a_{n-1}$ such that $r = \sum_{k=1}^{n-1} a_k k!$, and hence $m = \sum_{k=1}^n a_k k!$.

We’ve now seen that each of the $(n+1)!$ non-negative integers in $\{0,1,\dots,n\}$ has a representation of the form $\sum_{k=1}^n a_k k!$ with $0 \le a_k \le k$ for each $k$. However, there are only $\prod_{k=1}^n (k+1) = (n+1)!$ distinct representations of that form, so each must represent a different integer, and each integer’s representation is therefore unique.

You can also reason as follows : suppose you've shown for some integer $n$ that every integer $\in\lbrace0,\dots,n!-1\rbrace$ has a unique decomposition as you suggest. Take $k\in\lbrace0,\dots,(n+1)!-1\rbrace.$ Write $$k=q\cdot n!+r$$ the euclidean division of $k$ with respect to $n!$. Necessarily you have $0\leq q < n+1$. This gives you an expression you want, for $0\leq r<n!$ has, by hypothesis, an expression involving only factorials up to $(n-1)!$ .

Finally, to show uniqueness, you can again use your hypothesis to deduce that if $k=a_n\cdot n!+ \sum_0^{n-1} a_i\cdot i!,$ then $0\leq \sum\dots< n!-1$ by hypothesis, and this tells you that this decomposition is the euclidean division of $k$ by $n!$. So by uniqueness of the euclidean division, it's the one decomposition we defined earlier.

This generalizes to the representation $$n = \sum_{i\ge 0} a_i b_i$$ where $b_0 = 1$ and $b_{n+1} = b_n c_n$ with $c_n > 1$ and $0 \le a_i < c_i$ - i.e., representing $n$ with digits $a_i$ to a "base" with varying ratios of consecutive digit values (phrased awkwardly, I know, but it is late and I am tired). For a usual base $B$ system, $c_i = B$ for all $i$, so $b_i = B^i$. For this system, $c_i = i$ (or maybe $c_i = i+1$, modulo my tiredness), so $b_i = i!$.

I proved too many years ago that this representation is unique iff the $c_i$ were all integers. I am sure that this was proved many years ago (probably by Euler, if not Fermat) and is in Dickson somewhere.