n≥4 is an integer number. For any permutation x1,x2,⋯,xn of the numbers 1,2⋯,n we write the number x1+2x2+⋯+nxnon 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=201\cdot 3+2\cdot 4+3\cdot 2+4\cdot 1=211\cdot 3+2\cdot 4+3\cdot 1+4\cdot 2=221\cdot 4+2\cdot 2+3\cdot 1+4\cdot 3 =231\cdot 2+2\cdot 3+3\cdot 4+4\cdot 1=241\cdot 2 +2\cdot 4 + 3\cdot 1+ 4\cdot 3=251\cdot 1+2\cdot 4+3\cdot 3+4\cdot 2=261\cdot 1+2\cdot 3+3\cdot 4+4\cdot 2=271\cdot 2+2\cdot 1+3\cdot 4+4\cdot 3=281\cdot 2+2\cdot 1+3\cdot 3+4\cdot 4=291\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.