# A Combinatorics problem.

Problem: Let $n$ and $y$ be two positive integers such that $y\leq n!$.Then prove that there exist unique integers $x_1,x_2,...,x_{n-1}$ such that $0\leq x_i\leq n-i$ for $i=1,2,3,...,n-1$ and $y=1+ \sum_{i=1}^{n-1} x_i(n-i)!$.

My Proof: Let $(x_1,x_2,...,x_{n-1})$ be such a tuple ,then the number of all possible tuples satisfying $0\leq x_j\leq n-j$ for $j=1,2,...n-1$ is $n!$ and the number of all possible values of $y$ is also $n!$. The tuple corresponding to $y=1$ is $(0,0,...,0)$ and tuple corresponding to $y=n!$ is $(n-1,n-2,...,[n-(n-1)])$. All other tuples will correspond to some integer $1<y<n!$. I claim that each such tuple will correspond to a different value of $y$. Let's assume that $(d_1,d_2,...,d_{n-1})$ and $(r_1,r_2,...,r_{n-1})$ are two distinct tuples which correspond to the same value of $y$. Let $k$ be the max positive integer such that $d_k\neq r_k$ ,then our assumption implies that $d_1(n-1)!+d_2(n-2)!+...+d_k(n-k)!=r_1(n-1)!+r_2(n-2)!+...+r_k(n-k)!$. Which implies that $d_k=r_k mod (n-k+1)$, as$0\leq d_k\leq n-k$ and $0\leq r_k\leq n-k$ $|d_k-r_k|\leq n-k<n-k+1$ so the only possibility that remains is $d_k-r_k=0$ $→$ $d_k=r_k$ which contradicts our assumption that $d_k≠r_k$. $$QED$$ Is my proof correct?(I have not written some steps as they were cubersome to write) Please suggest any other approach. Is this a famous problem?

• The proof seems correct to me. It is surely not a famous problem. – k99731 Jan 3 '17 at 7:58

Another proof will be picking the minimum $k$.
Assuming $d_k > r_k$. Since $k$ is minimum, $n-k$ is maximum.
Also note that $\sum_{i=1}^{n-1} i*i! = n!-1$.
Therefore $(d_k-r_k) (n-k)! =\sum_{i=k+1}^{n-1} (r_i-d_i) (n-i)! \geq (n-k)!$.
However, $\sum_{i=k+1}^{n-1} (r_i-d_i) (n-i)! \leq \sum_{i=1}^{n-k-1} (i) (i)! = (n-k)!-1$. Contradiction.