Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When defining the parity of a permutation $f\in S_n$, one can use the "inversion number," $i(f)$ defined as the number of pairs $(i,j)$ with $i<j$ and $f(i)>f(j)$. One way of thinking about this number is the number of crosses in a diagram where we list the numbers from 1 to $n$ in two descending columns, and connect $i$ on the left with $f(i)$ on the right.

For example, the inversion number of $f=(1,3,5)(2,6)$ in $S_7$ is $i(f)=11$, corresponding to the pairs $(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6)$.

There is exactly one permutation in $S_n$ with $i(f)=0$, namely the identity, and one with largest possible value $i(f)=\displaystyle\binom n2$, namely $f(j)=n+1-j$, where all lines cross. In fact, for this $f$ and any $g$, $i( f\circ g)=\displaystyle\binom n2- i(g)$.

For $\displaystyle 0\le j\le\binom n2$ left $N(j)$ be the number of permutations $f$ in $S_n$ with $i(f)=j$. So $N(0)=N(\binom n2)=1$, and the last sentence from the previous paragraph shows that the graph of $N$ is symmetric about the line $j=\binom n2/2$.

I am looking for a proof that $N$ is unimodal (actually, strictly increasing up to $\lfloor \binom n2/2\rfloor$).

Also, any references on this subject would be appreciated.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Theorem 4.54 in Miklós Bóna, Introduction to Enumerative Combinatorics, says that for all $n\ge 2$, the generating function for the numbers $b(n,k)$ counting the number of permutations of $[n]$ with $k$ inversions is

$$\begin{align*}I_n(x)&=\sum_{p\in S_n}x^{i(p)}=\sum_{k=0}^{\binom{n}2}b(n,k)x^k\\\\ &=(1+x)(1+x+x^2)\dots(1+x+\dots+x^{n-1})\;.\tag{0} \end{align*}$$

A slightly messy but fairly straightforward induction on $n$ shows that the coefficients in these products are symmetric and unimodal.

Added: Here’s a brief sketch of the proof that Bóna gives; it’s by induction on $n$. Let $d(n,k)$ be the coefficient of $x^k$ in $(0)$; it’s clear that $d(2,0)=d(2,1)=b(2,0)=b(2,1)=1$. For the induction it suffices to show that $d$ and $b$ satisfy the same recurrence in $n$:

$$b(n,k)=b(n-1,k)+b(n-1,k-1)+\dots+b(n-1,m)\tag{1}$$

and

$$d(n,k)=d(n-1,k)+d(n-1,k-1)+\dots+d(n-1,m)\;,\tag{2}$$

where $m=\max\{0,k-n+1\}$. Verification of $(2)$ is straightforward.

To prove $(1)$, we must verify that its righthand side counts the number of permutations of $[n]$ with $k$ inversions. Suppose that $0\le i\le\min\{k,n-1\}$; $b(n-1,k-i)$ is the number of permutations of $[n-1]$ with $k-i$ inversions. Extend each of these to a permutation of $[n]$ by inserting $n$ in position $n-i$, so that it’s followed by $i$ members of the original permutation; this yields a permutation of $[n]$ with $(k-i)+i=k$ inversions. Since every permutation of $[n]$ with $k$ inversions is uniquely obtained in this way, we’ve established $(1)$.

share|improve this answer
    
Thanks for the reference and the argument. I am slow today, do you see a quick way of verifying this is the generating function? (Once we know this, unimodality and much more follow quickly.) –  Bruce George Mar 5 '12 at 1:06
    
@Bruce: It’s not hard: see my addition to my answer. –  Brian M. Scott Mar 5 '12 at 6:41
    
Yes, that works. Thanks! I was complicating things by writing permutations as products of cycles and seeing from this representation how inserting a new element affected the number of inversions. –  Bruce George Mar 5 '12 at 6:57

Let $[n]_q=1+q+q^2+\cdots+q^{n-1}$. This is usually called the $q$-analog of $n$. Then the permutations in $S_n$ enumerated according to inversion number have for generating function the $q$ analog of $n!$: $$[n]!_q=[1]_q [2]_q \cdots [n]_q.$$ Now use the fact that the product of unimodal palindromic polynomials (with coefficients in $\mathbb{Z}_{\geq 0}$) is unimodal and palindromic.

share|improve this answer
    
Thanks! It is a nice recursion. –  Bruce George Mar 5 '12 at 6:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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