Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. Jul 23 '11 at 11:56
add comment

4 Answers

up vote 7 down vote accepted

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

share|improve this answer
    
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
1  
@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
1  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.