$n\geq 4$ is an integer number. For any permutation $x_1,x_2,\cdots,x_n$ of the numbers $1,2 \cdots,n$ we write the number $$ x_1+2x_2+\cdots+nx_n $$on the board. Compute the number of total distinct numbers written on the board.
Problem
Source: Iran 3rd round 2024 Combinatorics exam P1
Tags: combinatorics
sami1618
30.08.2024 01:10
Answer: $\binom{n+1}{3}+1$
$$1\cdot 4+2\cdot 3+3\cdot 2+4\cdot 1=20$$$$1\cdot 3+2\cdot 4+3\cdot 2+4\cdot 1=21$$$$1\cdot 3+2\cdot 4+3\cdot 1+4\cdot 2=22$$$$1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 3 =23$$$$1\cdot 2+2\cdot 3+3\cdot 4+4\cdot 1=24$$$$1\cdot 2 +2\cdot 4 + 3\cdot 1+ 4\cdot 3=25$$$$1\cdot 1+2\cdot 4+3\cdot 3+4\cdot 2=26$$$$1\cdot 1+2\cdot 3+3\cdot 4+4\cdot 2=27$$$$1\cdot 2+2\cdot 1+3\cdot 4+4\cdot 3=28$$$$1\cdot 2+2\cdot 1+3\cdot 3+4\cdot 4=29$$$$1\cdot 1+2\cdot 2+3\cdot 3+4\cdot 4=30$$
Now lets go from $n\rightarrow n+1$. Then letting $x_{n+1}=n+1$ each sum increases by $(n+1)^2=\tbinom{n+1}{2}+\tbinom{n+2}{2}$ so every sum in the range $$\left[\binom{n+1}{2}+\binom{n+2}{2}+\binom{n+2}{3},\binom{n+1}{2}+\binom{n+2}{2}+\binom{n+2}{3}+\binom{n+1}{3}\right ]=\left[\binom{n+1}{2}+\binom{n+3}{3},\binom{n+3}{3}+\binom{n+2}{3}\right]$$is achievable. And letting $x_{n+1}=1$ and increasing every other element by $1$, each sum increases by $\binom{n+2}{2}$ so every sum in the range $$\left[\binom{n+2}{2}+\binom{n+2}{3},\binom{n+2}{2}+\binom{n+2}{3}+\binom{n+1}{3}\right]=\left[\binom{n+3}{3}, \binom{n+3}{3}+\binom{n+1}{3}\right]$$is achievable. As $n\geq 4$, these ranges intersect to give the desired range, thus we are done.