1
$\begingroup$

Let: $P_n(x) = 1(1+x)(1+x+x^2)+ \dots +(1+x+x^2+ \dots +x^n)$

I heard that the $k$-th coefficient of $P_n(x)$ is the number of permutations $\sigma \in S_n$ with $k$ inversions and I want to prove that, but I got stuck.

My work:

The $k$-th coefficient of $P_n(x)$ (which I will call $c_k$) is the number of ways in which we can choose a term of the form $x^a$ from each paranthesis such that their product is $k$. We will call the term we choose from the $i$-th paranthesis $x^{a_i}$. This means that: $$ c_k = |\{ (a_i)_{0\leq i\leq n} | a_i \leq i, a_i \in \mathbb{N}, \sum a_i = k\}|$$

Let $\sigma \in S_n$ such that $\sigma$ has $k$ inversions and $A_i = |\{ j | j < i, \sigma(j) > \sigma(i) \}|$. That means that: $$\sum A_i = k$$

So what I need to prove is that: $$c_k = \sum A_i$$ which I don't know how to do. Can you help me?

$\endgroup$
1
$\begingroup$
  1. A correction: the number of permutations $\sigma\in S_n$ with $k$ inversions (let's still denote this number by $c_k$) is equal to the coefficient of $x^k$ in $P_{\color{red}{n-1}}(x)=(1+x)\ldots(1+x+\ldots+x^{\color{red}{n-1}})$.
  2. Writing your $A_i$ as functions of $\sigma$, the crucial fact is that the map $\sigma\mapsto\big(\color{gray}{A_1(\sigma),{}}A_2(\sigma),\ldots,A_n(\sigma)\big)$ is a bijection between $S_n$ and $\color{gray}{[0,1)\times{}}[0,2)\times\ldots\times[0,n)$: given a tuple $(\color{gray}{a_1,{}}a_2,\ldots,a_n)$ of integers satisfying $0\leqslant a_k\leqslant k-1$ for $1\leqslant k\leqslant n$, one can construct a permutation $\sigma$ with $A_k(\sigma)=a_k$.
  3. "So what I need to prove is..." - not quite, thus. From "2.", $c_k$ is the number of tuples $(a_1,\ldots,a_n)$ with $0\leqslant a_i\leqslant i-1$ and $a_1+\ldots+a_n=k$. Which, as we see, is exactly what's stated in "1.".
$\endgroup$
  • $\begingroup$ That's a really nice line of reasoning. Especially the fact that the function you constructed is a bijection, which makes sense after thinking a little about it. Thanks $\endgroup$ – Lazar Ionut Radu Sep 15 '19 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.