# Getting generating functions for a weirdly-defined weight function

Let $n\in\mathbb{N}$. For a permutation $\sigma:[n]\rightarrow[n]$, we ue the notation $(\sigma(1)\sigma(2)\cdots\sigma(n))$ to describe the mapping. A pair of integers $(i,j)$ is called an inversion of $\sigma$ if $i<j$ and $\sigma(i)>\sigma(j)$. For example, the permutation $(32415)$ on $[5]$ has 4 inversions: $(1,2),(1,4),(2,4),(3,4)$. Define the weight function $w$ on a permutation $\sigma$ to be the number of inversions in $\sigma$. Let $S_n$ be the set of all permutations of $[n]$.

(a) Determine the generating functions for $S_1$, $S_2$, $S_3$ with respect to the weight function $w$.

(b) Prove that for $n\geq 2$, $\Phi_{S_{n}}(x)=(1+x+\cdots+x^{n-1})\Phi_{S_{n-1}}(x)$. You may use the following non-standard notation: if $\sigma$ is a permutation of $[n]$, then $\sigma '$ is the permutation of $[n-1]$ obtained from $\sigma$ by removing the element $n$.

(c) Prove that the number of permutations of $[n]$ with $k$ inversions is

$$[x^{k}]\frac{\prod_{i=1}^{n}(1-x^{i})}{(1-x)^{n}}$$

(a) is doable by brute-forcing. (b) seems to be doable by the product lemma if only the weight function was something more tractable, since I need to prove that the weight is equal to adding the weights of some product. (c) is completely over my head since I can't get any general formula for the number of inversions in a permutation.

• There is some material here that you may want to consult. This post could be relevant. – Marko Riedel May 30 '13 at 20:46

If you have (a) and (b), you have (c):

\begin{align*} \frac1{(1-x)^n}\prod_{i=1}^n(1-x^i)&=\prod_{i=1}^n\frac{1-x^i}{1-x}\\\\ &=\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)\;, \end{align*}

so you need only verify that $\Phi_{S_1}(x)=1$.

One way to prove that

$$\Phi_{S_n}(x)=\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)$$

is by induction on $n$: let $$c_n(k)=[x^k]\Phi_{S_n}(x)\;,$$ the number of $n$-permutations with $k$ inversions, and $$a_n(k)=[x^k]\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)\;,$$ and show that

$$c_n(k)=\sum_{i=\max\{0,k-n+1\}}^kc_{n-1}(i)\tag{1}$$

and

$$a_n(k)=\sum_{i=\max\{0,k-n+1\}}^ka_{n-1}(i)\;.\tag{2}$$

$(2)$ is pretty straightforward. For $(1)$, think about starting with a permutation of $[n-1]$ with $i$ inversions and inserting $n$ so that it precedes the last $k-i$ elements of the permutation; how many inversions does that add to the permutation? (The non-standard notation mentioned in (b) appears to be designed to let you talk easily about the inverse of this operation.)

• Just to clarify - I don't have (b). – ithisa May 30 '13 at 20:48
• @Eric: I realize that. The first part of the answer is just pointing out that (c) won’t be a problem once you do have (b). The part starting One way to prove ... is really about proving (b), though I didn’t phrase it quite that way: (a) and (b) together are equivalent to $$\Phi_{S_n}(x)=\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)\;.$$ – Brian M. Scott May 30 '13 at 20:50