3
$\begingroup$

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 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.

2 Answers 2

1

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)$.

  • 0
    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.2012-03-05
1

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.

  • 0
    Thanks! It is a nice recursion.2012-03-05