Summations involving permutations

Question

Let $n \geq 3$ be an integer.For a permutation $P =(a_1,a_2,\cdots,a_n)$ of $(1,2,\cdots,n)$ we let $fP(x)=a_nx^{n-1}+a_{n-1}x^{n-2}+\cdots+a_2x+a_1$.Let $SP$ be the sum of the roots of $fP(x)=0$ and let $S$ denote the sum over all permutation P of $(1,2,\cdots,n)$ of the number $SP$.Then----

A) $S<-n!$

B)$-n!<S<0$

C)$0<S<n!$

D)$n!<S$

My attempt---

$SP=- \frac{a_{n-2}}{a_n}$

Total number of ways of arranging $a_{n-2},a_n$ is $\binom n2.2$

Hence the sum should have been $$\sum_{a_{n-2}=1}^{n} \sum_{a_n=1}^{n} -\frac{a_{n-2}}{a_n}$$ .The summation evaluated to $$\frac{n(n+1)}2 [1+1/2+\cdots+1/n]$$.

I could not find out the correct option after doing all this.

Any help appreciated. Thanks.

Answer 1

1. For any permutation $\sigma$ on $\{1,2,\dots,n\}$, Vieta says that the sum of the roots of the polynomial $$ P_\sigma(x)=\sum_{k=1}^n\sigma(k)x^{k-1}\tag{1} $$ is $-\frac{\sigma(n-1)}{\sigma(n)}$.

2. There are $(n-2)!$ permutations with a given $\sigma(n-1)$ and $\sigma(n)$.

3. The sum of $-\frac{\sigma(n-1)}{\sigma(n)}$ over all possible values of $\sigma(n-1)$ and $\sigma(n)$ is $$ \sum_{k=1}^nk\sum_{k=1}^n\frac1k-n=\frac{n^2+n}2H_n-n\tag{2} $$ where $H_n$ is the $n^{\text{th}}$ Harmonic Number. We subtract $n$ since $\sigma(n-1)\ne\sigma(n)$.

Incorporating points 1, 2, and 3, we get $$ \begin{align} S(n) &=\sum_{\sigma\in\mathcal{P}_n}-\frac{\sigma(n-1)}{\sigma(n)}\\ &=-(n-2)!\left(\frac{n^2+n}2H_n-n\right)\tag{3} \end{align} $$ where $\mathcal{P}_n$ is the set of permutations on $\{1,2,\dots,n\}$.

---

$S(2)=-\frac52\lt-2=-2!$

$S(3)=-8\lt-6=-3!$

For $n\ge4$, we have $H_n\gt2$. Thus, $S(n)\lt-n^2(n-2)!\lt-n!$

Therefore, for $n\ge2$, we have $S(n)\lt-n!$

Answer 2

For $i, j \in \{1, ..., n\}$ two integers, there are $(n-2)!$ permutations where $a_{n-1} = i$ and $a_n = j$, so you would have something like : $$\sum_{a_n = 1}^n \sum_{a_{n-1}=1}^n-{a_{n-1}\over a_n}(n-2)!$$

However with such a sum you count permutations that don't exist where $a_n = a_{n-2}$. Thankfully, these terms are easy to calculate and you can substract them, thus :

$$\begin{align} S &= \sum_{a_n = 1}^n \sum_{a_{n-1}=1}^n-{a_{n-1}\over a_n}(n-2)! + n(n-2)!\\ &=-(n-2)!\left(\sum_{a_n = 1}^n \sum_{a_{n-1}=1}^n{a_{n-1}\over a_n}-n\right)\\ &=-(n-2)!\left(\sum_{a_n = 1}^n {n(n+1)\over 2a_n}-n\right)\\ &=-n(n-2)!\left({(n+1)\over2}\sum_{a_n = 1}^n {1\over a_n}-1\right)\\ \end{align}$$

And since $$\sum_{a_n = 1}^n {1\over a_n} \ge \sum_{a_n = 1}^n {1\over n} = 1$$ We always have $S\le0$

To compare $S$ to $-n!$ we need to compare ${(n+1)\over2}\sum_{a_n = 1}^n {1\over a_n}$ to $n$, ie $\sum_{a_n = 1}^n {1\over a_n}$ to ${2n\over n+1} =2 - {2\over{n+1}}$.

What follows is that $$\sum_{a_n = 1}^n {1\over a_n}\gt 2-{2\over n+1}$$ for all $n\ge3$

Thus $$S \le n!$$.