OMC235(F) - f(n)の求め方別解

各$1 \leq i \leq n$について$\max(a_1,a_2,\dots,a_i)=j$であるような場合の数は$\displaystyle\binom{j-1}{i-1}i!(n-i)!$なので、 $$\begin{aligned} f(n)&=\displaystyle\sum_{i=1}^n \sum_{j=i}^n j\binom{j-1}{i-1}i!(n-i)! \\ &=\sum_{i=1}^n i \times i!(n-i)! \sum_{j=i}^n \binom{j}{i} \\ &=\sum_{i=1}^n \binom{n+1}{i+1}\times i \times i!(n-i)! \\ &=\sum_{i=1}^n (n+1)!\frac{i}{i+1} \end{aligned}$$ である。