Factorial decomposition of integers?

Question

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 ?

Thanks in advance

Answer 1

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.)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

It is really easy to see why the representation is unique. It is analogous to finding the representation of a number in a different base. For example, to find the base 3 representation of n, you do the following:

1. Get the next digit by finding n mod 3
2. Do an integer divide of n by 3
3. If n > 0 then go to step 1

In the case of factorial sums, do the following:

1. Set i = 2
2. The next digit is n mod i
3. Do an integer divide of n by i
4. If n > 0, set i = i + 1 and go to step 2