\documentstyle{amsppt}
\NoBlackBoxes
\magnification=1200
\baselineskip=11pt
\newcount\sectno
\newcount\thmno
\define\secthead#1{\global\advance\sectno by 1
\bigpagebreak\par\noindent {\bf Section \the\sectno. #1}\bigpagebreak\par}
\define\nextthm{\global\advance\thmno by 1
\the\thmno}
\define\rem#1{\vskip .2truein \par \noindent {\bf #1} \newline}
\define\endrem{\vskip .2truein}
\define\endproof{$\qed$\enddemo}
\define\sq{\square}
\define\Pos{\Bbb P}
\define\Nonneg{\Bbb N}
\define\Int{\Bbb Z}
%\input ferrer.tex
\topmatter
\title Characters and inversions in the symmetric group
\endtitle
\author Anne de M\'edicis,
Victor Reiner,
%\footnote{work partially supported by NSF Mathematical
%Sciences Postdoctoral Research Fellowship DMS-9206371}
Mark Shimozono
\endauthor
\affil Department of Mathematics \\ University of Minnesota \\ Minneapolis, MN 55455
\endaffil
\email demedic@math.umn.edu, reiner@math.umn.edu, mshimo@math.umn.edu
\endemail
\date November 1993
\enddate
\endtopmatter
\noindent
{\bf Abstract}
\newline
We consider sums of the form
$$\sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \,\, q^{inv(\pi)}$$
where $\chi^{\lambda/\mu}$ is a skew character of the symmetric group
and $inv(\pi)$ is the number of inversions of $\pi$.
Our main result gives a lower bound on the number of
factors of $1+q$ and $1-q$ which divide the above
sum, and is shown to be sharp when
$\lambda/\mu$ is a hook partition shape.
\vskip 2cm
\noindent
{\bf R\'esum\'e}
\newline
Nous consid\'erons des sommes de la forme
$$\sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \,\, q^{inv(\pi)}$$
o\`u $\chi^{\lambda/\mu}$ est un caract\`ere gauche du groupe
sym\'etrique et $inv(\pi)$ d\'esigne le nombre d'inversions de $\pi$.
Notre r\'esultat principal donne une borne inf\'erieure pour le nombre de
facteurs $(1+q)$ et $(1-q)$ qui divisent ces sommes. Nous d\'emontrons en
particulier que cette borne est exacte lorsque $\lambda/\mu$ est une \'equerre.
\newpage
\secthead{Introduction}
In this paper, we consider sums over the symmetric group $S_n$
of the form
$$\sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \, q^{inv(\pi)}$$
where $\chi^{\lambda/\mu}$ is a {\it skew character} of the symmetric group
\cite{JP} and $inv(\pi)$ is the number of inversions of $\pi$,
i.e.
$$inv(\pi) = \#\{(i,j): 1 \leq i < j \leq n ,
\,\, \pi^{-1}(i) > \pi^{-1}(j) \}.$$
There are two motivations for considering such sums. Firstly, other
than some special results of Gessel \cite{Ge} and Edelman
\cite{Ed}, there is very little known about the
joint distribution of inversions and conjugacy class (i.e. cycle type)
in $S_n$. This is in stark contrast to the joint distributions
known for inversions and descent statistics \cite{GaGe}, and for
cycle type and descent statistics \cite {GR}. Thus it seems reasonable to ask what can be said about the sum
$$\sum_{\pi \in S_n} f(\pi) \, q^{inv(\pi)}$$
when $f$ is some {\it class function}, i.e. a function which
is constant on conjugacy classes in $S_n$, such as an irreducible
character $\chi^{\lambda}$.
\rem{Remark} As pointed out by the referee,
there is a different interpretation one can attach to these
sums, namely that
$$\sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \, q^{inv(\pi)}
= \langle s_{\lambda/\mu}, F_n \rangle$$
where $\langle, \rangle$ is the usual
{\it Hall inner product} on symmetric functions, $s_{\lambda/\mu}$
is the {\it skew Schur function} corresponding to $\lambda/\mu$,
and $F_n$ is a certain symmetric function with coefficients in {\bf Z}$[q]$
which encodes all the information about the distribution of inversions
and conjugacy class in $S_n$:
$$
F_n:=\sum_{\pi \in S_n} q^{inv(\pi)} p_{\lambda(\pi)}
$$
where $p_\lambda(\pi)$ is the {\it power sum} symmetric function
corresponding to the cycle type of $\pi$ (see \cite{Mac}).
\endrem
The second motivation
is by analogy to the work of \cite{DF,Re}. Here it was shown
that sums of the form
$$ \sum_{\pi \in W} \chi(w) \, q^{des(\pi)}$$
have high divisibility by linear polynomial factors,
where $W$ is a classical Weyl group, $\chi$ is a one-dimensional
character of $W$, and $des$ is the {\it descent} statistic on $W$.
Our main theorem is the following
\proclaim{Theorem \nextthm{}}
Let $\lambda/\mu$ be a skew shape with longest row of length $r$
and longest column of length $s$. Then
$$\sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \,\, q^{inv(\pi)} $$
is divisible by
$$(1+q)^{\lfloor r/2 \rfloor}
(1-q)^{\lfloor s/2 \rfloor}.$$
\endproclaim
This Theorem is proven in Section 2.
The divisibilities asserted by the previous theorem
are sometimes tight, as demonstrated by
\proclaim{Theorem \nextthm{}}
If $\lambda$ is a {\it hook partition} $(r,1^{s-1})$ then
$$
\aligned
\sum_{\pi \in S_n} \chi^{\lambda}(\pi) \,\, q^{inv(\pi)}
&= (1-q)^{\lfloor s/2 \rfloor} S(q) \\
&= (1+q)^{\lfloor r/2 \rfloor} R(q)
\endaligned
$$
where $S(q), R(q) \in \Int[q]$ satisfy
$$S(1) = \left\{
\matrix
{(n+1)! \lfloor s/2 \rfloor ! \over (s+1)!} & s \text{ is even} \\
{n! \lfloor s/2 \rfloor ! \over s!} & s \text{ is odd}
\endmatrix \right.
$$
and
$$R(-1) = \left\{
\matrix
{(n+1)! \lfloor r/2 \rfloor ! \over (r+1)!} & r \text{ is even} \\
{n! \lfloor r/2 \rfloor ! \over r!} & r \text{ is odd}
\endmatrix \right.
$$
\endproclaim
This is proven in Section 2. It is also conjectured there that
$S(q)$ has non-negative coefficients whenever $r \geq s$.
In Section 3, we look more closely at the very special case $s=2$
where can prove this conjecture by a very interesting bijection.
In this special case, the results relate to the joint distribution
of fixed points and inversions over the symmetric group.
\secthead{Proof of Theorem 1}
Theorem 1 will follow by a sequence of straightforward
reductions from the following lemma, which appears to
be the essence of the divisibilities appearing in this context.
Notation: for $A \subseteq [n]$, let $S_A$ be the subgroup
of permutations in $S_n$ which only permute within the elements
of $A$ and fix all elements of $[n]-A$.
\proclaim{Lemma \nextthm{}}
Fix a subset $A \subseteq [n]$ having cardinality $r$
and fix any permutation $\sigma \in S_{[n]-A}$.
Then
$$\sum_{\pi \in S_A} q^{inv(\pi\sigma)}$$
is divisible by
$(1+q)^{\lfloor r/2 \rfloor}$
\endproclaim
\demo{Proof:}
Make a change of variable to $p=1+q$. We
need to show $p^{\lfloor r/2 \rfloor}$ divides
$$
\aligned
\sum_{\pi \in S_A} (p-1)^{inv(\pi\sigma)}
&=\sum_{\pi \in S_A \atop J \subseteq Inv(\pi)}
p^{\#J}(-1)^{inv(\pi\sigma)-\#J} \\
&=\sum_{J \subseteq \left( [n] \atop 2 \right)}
(-1)^{inv(\sigma)+\#J} p^{\#J}
\sum_{\pi \in S_A \atop J \subseteq Inv(\pi)} (-1)^{inv(\pi)}
\endaligned
$$
Here $Inv(\pi)$ denotes the {\it inversion set} of $\pi$, that is
$$
Inv(\pi) = \{(i,j): 1 \leq i < j \leq n ,
\, \pi^{-1}(i) > \pi^{-1}(j) \}
$$
So it suffices to show that for any $J \subseteq \left( [n] \atop 2 \right)$
with $\#J < \lfloor r/2 \rfloor$ we have
$$\sum_{\pi \in S_A \atop J \subseteq Inv(\pi)} (-1)^{inv(\pi)} = 0$$
Since $2 \#J \leq r-2$, there must exist a pair
$i,j \in A$ which are not involved in any of the pairs in $J$, and
hence multiplication on the left by the transposition $(i j)$ is a
sign-reversing involution which shows all terms in the above sum cancel.
\endproof
\rem{Remark}
The preceding lemma bears some resemblance to results of
Bj\"orner and Wachs \cite{BW} on the distribution of inversions
over certain subsets of $S_n$ which they call {\it generalized quotients}.
In particular, for certain of these generalized quotients, they
produce nice hook-formula factorizations
for the generating function of inversions,
which naturally have high divisibility by $(1+q)$. It would
be desirable to understand this connection better.
\endrem
\demo{Proof of Theorem 1}
We wish to show that if $\lambda/\mu$ is a skew shape with
longest row of length $r$ and longest column of length $s$, then
$$\sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \,\, q^{inv(\pi)} $$
is divisible by
$$(1+q)^{\lfloor r/2 \rfloor}
(1-q)^{\lfloor s/2 \rfloor}.$$
Our strategy will be to reduce the theorem to a very special case
and then apply the Lemma.
First note that if $({\lambda/\mu})^t$ denotes the skew shape which
is the {\it transpose} of ${\lambda/\mu}$, then
$$
\aligned
\sum_{\pi \in S_n} \chi^{({\lambda/\mu})^t}(\pi) \,\, q^{inv(\pi)}
&= \sum_{\pi \in S_n}
\chi^{\lambda/\mu}(\pi) \,\, sgn(\pi) \,\, q^{inv(\pi)} \\
&= \sum_{\pi \in S_n}
\chi^{\lambda/\mu}(\pi) \,\, (-q)^{inv(\pi)}
\endaligned
$$
using the fact that
$$\chi^{({\lambda/\mu}^t)} (\pi) = \chi^{\lambda/\mu}(\pi) \,\, sgn(\pi)$$ Therefore it suffices to show only divisibility
by $(1+q)^{\lfloor r/2 \rfloor}$.
Using the Littlewood-Richardson rule \cite{Sa}, one knows that
$$\chi^{\lambda/\mu}(\pi) = \sum_{\nu} \chi^{\nu}(\pi)$$
where the sum ranges over a {\it multiset} of partitions $\nu$ which all have
longest part of size at least $r$. Then using the Jacobi-Trudi identity \cite{Sa}, one can write
$$\chi^{\nu}(\pi) = \sum_{\rho} \pm \chi^{H(\rho)} (\pi)$$
Here $\rho$ runs over a set of partitions of $n$, and $H(\rho)$ is
the skew diagram having disjoint horizontal rows of size $\rho_i$ for
each $i$. A picture of $H(5,4,2,2)$ is shown below:
%$$\centerline{\vbox{
%\btableaux{l}
%\advance\bxdir by 8
%\plbox{\ }\plbox{\ }\plbox{\ }\plbox{\ }\plbox{\ }
%\bxdir=4 \advance\bydir by -1
%\plbox{\ }\plbox{\ }\plbox{\ }\plbox{\ }
%\bxdir=2 \advance\bydir by -1
%\plbox{\ }\plbox{\ }
%\bxdir=0 \advance\bydir by -1
%\plbox{\ }\plbox{\ }\nbox
%\etableaux}}$$
Furthermore, expanding the Jacobi-Trudi determinant along its
top row tells us that each $\rho$ appearing in the above sum
will have its largest part $\rho_1$ of size at least $r$.
Since we are only trying to show
divisibility by $(1+q)^{\lfloor r/2 \rfloor}$, it therefore
suffices to prove the theorem in the special case where
$\lambda/\mu = H(\rho)$ for some partition $\rho$ with largest part of size $r$.
The character $\chi^{H(\rho)}$ is easy to write down explicitly,
as it is the character of the {\it permutation representation}
of $S_n$ acting on the left cosets of the Young subgroup $S_\rho$
which permutes the first $\rho_1$ numbers among themselves, permutes
the next $\rho_2$ among themselves, etc. So $\chi^{H(\rho)}(\pi)$ is
the number of such left cosets fixed by $\pi$. Therefore,
$$
\aligned
\sum_{\pi \in S_n} \chi^{H(\rho)}(\pi) \,\, q^{inv(\pi)}
&= \sum_{\pi \in S_n}
\#\{\text{cosets }\tau S_\rho: \pi \tau S_\rho = \tau S_\rho\}
\,\, q^{inv(\pi)} \\
&= \sum_{\text{cosets }\tau S_\rho}
\sum_{\pi \in S_n \atop \pi \tau S_\rho = \tau S_\rho}
\,\, q^{inv(\pi)} \\
&=\sum_{(A_1,\ldots,A_k) \atop \uplus A_i = [n], \#A_i=\rho_i}
\sum_{(\pi_1,\ldots,\pi_k) \atop \pi_i \in S_{A_i}}
\,\, q^{inv(\pi_1 \cdots \pi_k)} \\
&=\sum_{(A_1,\ldots,A_k) \atop \uplus A_i = [n], \#A_i=\rho_i}
\sum_{(\pi_2,\ldots,\pi_k) \atop \pi_i \in S_{A_i}}
\sum_{\pi_1 \in S_{A_1}}
\,\, q^{inv(\pi_1 \sigma)}
\endaligned
$$
where $\sigma = \pi_2 \cdots \pi_k$ in the last summation.
By the Lemma, each of these sums
$$\sum_{\pi_1 \in S_{A_1}}
\,\, q^{inv(\pi_1 \sigma)}$$
are divisible by $(1+q)^{\lfloor r/2 \rfloor}$, and hence
the theorem is proven.
\endproof
\rem{Remark}
At least some of the divisibility asserted by Theorem 1 is immediate,
namely that for $s \geq 2$ the sum is divisible by $(1-q)^1$, and
by the transpose symmetry, for $r \geq 2$ the sum is divisible by $(1+q)^1$.
We simply note that by the Littlewood-Richardson rule, for $s \ge 2$,
$\chi^{\lambda/\mu}$ does not contain the trivial character in
its irreducible decomposition, and hence by the orthogonality
relation for characters, we have
$$\left[
\sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \,\, q^{inv(\pi)}
\right]_{q=1}
= \sum_{\pi \in S_n} \chi^{\lambda/\mu}(\pi) \cdot 1(\pi)
= 0
$$
This implies the sum is divisible by $(1-q)^1$.
\endrem
\secthead{Proof of Theorem 2}
We only give a sketch of the proof.
To begin, we note that our earlier comment about the effect of
transposing the shape $\lambda/\mu$ on the sum implies that
we only need to prove that $S(1)$ has the asserted value.
We will proceed by descending induction on $r$, beginning with
the base case $r=n$. Note that in this case $\chi^{(r,1^{s-1})}$
is the trivial character and
$$
\sum_{\pi \in S_n} q^{inv(\pi)}
= [n]!_q = [n]_q [n-1]_q \cdots [2]_q [1]_q
$$
where $[n]_q = 1 + q + q^2 + ... + q^{n-1}$.
The theorem then immediately follows in this case from the
above expression.
For the inductive step, our strategy will be to replace
$\chi^{(r,1^{s-1})}$ with a character we can compute more explicitly.
Let $(1^{s-1}) \oplus (r)$ denote the skew shape which
has a column of size $s-1$ disjoint from a row of size $r$ as shown
below for $r=4, s=6$:
%$$\centerline{\vbox{
%\btableaux{l}
%\advance\bxdir by 1
%\plbox{\ }\plbox{\ }\plbox{\ }\plbox{\ }\nbox
%\plbox{\ }\nbox
%\plbox{\ }\nbox
%\plbox{\ }\nbox
%\plbox{\ }\nbox
%\plbox{\ }\nbox
%\etableaux}}$$
By an easy case of the Littlewood-Richardson rule,
$$\chi^{(1^{s-1}) \oplus (r)} = \chi^{(r,1^{s-1})} + \chi^{(r+1,1^{s-2})}$$
and hence
$$\chi^{(r,1^{s-1})} = \chi^{(1^{s-1}) \oplus (r)} - \chi^{(r+1,1^{s-2})}$$
Using the last equation, one can check that the inductive step is
equivalent to proving the following:
$$
\left[ {\sum_{\pi \in S_n} \chi^{(1^{s-1}) \oplus (r)}(\pi) \,\, q^{inv(\pi)}
\over (1+q)^{\lfloor r/2 \rfloor} } \right]_{q=-1}
=
\left\{
\matrix
{(n+2) n! \lfloor r/2 \rfloor ! \over (r+1)!} & r \text{ is even} \\
{n! \lfloor r/2 \rfloor ! \over r!} & r \text{ is odd}
\endmatrix \right.
$$
To prove the last expression, we make the change of
variable $p=1+q$ as before, and we will use the fact that the character
$\chi^{(1^{s-1}) \oplus (r)}$ is the induction from $S_{s-1} \times S_r$
to $S_n$ of the character $sgn \otimes 1$. We then have
$$
\aligned
&\left[ {\sum_{\pi \in S_n} \chi^{(1^{s-1}) \oplus (r)}(\pi) \,\, q^{inv(\pi)}
\over (1+q)^{\lfloor r/2 \rfloor} } \right]_{q=-1} \\
&=
\left[ {\sum_{\pi \in S_n} \chi^{(1^{s-1}) \oplus (r)}(\pi)
\,\, (p-1)^{inv(\pi)}
\over p^{\lfloor r/2 \rfloor} } \right]_{p=0} \\
&=
\left[ p^{-\lfloor r/2 \rfloor} \sum_{\pi \in S_n}
\sum_{A \in \left([n] \atop s-1 \right) \atop \pi(A)=A} sgn(\pi|_A)
(p-1)^{inv(\pi)} \right]_{p=0} \\
&=
\left[ p^{-\lfloor r/2 \rfloor} \sum_{\pi \in S_n}
\sum_{A \in \left([n] \atop s-1 \right) \atop \pi(A)=A} sgn(\pi|_A)
\sum_{J \subseteq \left([n] \atop 2 \right) \atop J \subseteq Inv(\pi)}
p^{\#J}(-1)^{inv(\pi)-\#J} \right]_{p=0} \\
&=
(-1)^{\lfloor r/2 \rfloor}
\sum_{A \in \left([n] \atop s-1 \right), \,
J \subseteq \left([n] \atop 2 \right)
\atop \#J = \lfloor r/2 \rfloor}
\sum_{\pi \in S_n \atop \pi(A) = A, \, J \subseteq Inv(\pi)}
sgn(\pi|_{[n]-A})
\endaligned
$$
The proof then proceeds by finding a sequence of relatively
simple sign-reversing involutions which sieve the above sum
down to a small set of terms, each having sign
$(-1)^{\lfloor r/2 \rfloor}$. and having the desired cardinality
to prove the assertion.
\endproof
The data suggests that even more is true in the hook case:
\proclaim{Conjecture \nextthm{}}
Let $\lambda$ be a {\it hook partition} $(r,1^{s-1})$, and $S(q)$
as before, i.e
$$
\aligned
\sum_{\pi \in S_n} \chi^{\lambda}(\pi) \,\, q^{inv(\pi)}
&= (1-q)^{\lfloor s/2 \rfloor} S(q) \\
\endaligned
$$
If $r \geq s$, then $S(q)$ has non-negative coefficients.
\endproclaim
\secthead{The defining representation}
When $s=2$, the character $\chi^{(r,1^{s-1})}$ is essentially the
{\it defining character} of $S_n$, i.e. the permutation representation
of $S_n$ acting on $[n]$. This character has the
particularly simple expression
$$\chi^{(n-1,1)}(\pi) = \#Fix(\pi)-1$$
where $Fix(\pi)$ is the set of {\it fixed points} or
$1$-cycles of $\pi$ i.e.
$$Fix(\pi) = \{k: 1 \leq k \leq n, \,\, \pi_k = k\}$$
Therefore our results in this case have interpretations
in terms of the joint distribution of fixed points and
inversions over the symmetric group, some of which are
interesting. For example, it is well-known
and easy to see that ``the average permutation
in $S_n$ has one fixed point" and
``the average permutation in $S_n$ has
${1 \over 2} \left( n \atop 2 \right)$ inversions".
The following corollary asserts that the value of
$\#Fix(\pi) \cdot inv(\pi)$ for the ``average
permutation $\pi$ in $S_n$" is
$${(3n+1)(n-2) \over 12}$$
\proclaim{Corollary \nextthm}
$$\sum_{\pi \in S_n} \#Fix(\pi) \cdot inv(\pi)
= {(3n+1)(n-2) \over 12} n!$$
\endproclaim
\demo{Proof}
Let $f(q)$ denote the sum
$$\sum_{\pi \in S_n} \chi^{(n-1,1)}(\pi) \, q^{inv(\pi)}
= \sum_{\pi \in S_n} (\#Fix(\pi)-1) \, q^{inv(\pi)}$$
Then we have
$$
\aligned
S(1)
&= {lim \atop q \rightarrow 1} \left( {f(q) \over 1-q} \right) \\
&= \left[ {d \over dq} f(q) \right]_{q=1} \\
&= \sum_{\pi \in S_n} (\#Fix(\pi)-1) \cdot inv(\pi)
\endaligned
$$
By Theorem 2 in the case $s=2$, we have
$S(1) = (n+1)!/6$. Combining this with the easy fact
that
$$
\sum_{\pi \in S_n} inv(\pi) =
\left( n \atop 2 \right) {n! \over 2}
$$
gives the result.
\endproof
The preceding result can be considerably strengthened:
\proclaim{Proposition \nextthm{}}
$$\sum_{\pi \in S_n} \#Fix(\pi) \,\, q^{inv(\pi)}=
\sum_{k=1}^{n}[k-1]!_q [n-k]!_q
\sum_{j \geq 0} q^{j^2+2j}
\left[ k-1 \atop j \right]_q
\left[ n-k \atop j \right]_q
$$
where
$$\left[ n \atop k \right]_q = {[n]!_q \over [k]!_q [n-k]!_q}$$.
\endproclaim
\demo{Proof}
$$
\aligned
\sum_{\pi \in S_n} \#Fix(\pi) \,\, q^{inv(\pi)}
&= \sum_{k=1}^{n} \sum_{\pi \in S_n \atop \pi_k = k} q^{inv(\pi)} \\
&= \sum_{k=1}^{n} \,\, \sum_{\sigma \in
S_{[1,k-1]} \times S_{\{k}\} \times S_{[k+1,n]}} q^{inv(\sigma)}
\sum_{\tau \in S_n, \, \tau_k=k \atop
\tau_1 < \cdots \tau_{k-1}, \, \tau_{k+1} < \cdots \tau_{n}}
q^{inv(\tau)}
\endaligned
$$
where the last equality comes from the well-known fact that any
permutation $\pi$ may be factored uniquely as $\pi = \sigma \tau$
with $\sigma \in S_{[1,k-1]} \times S_{\{k\}} \times S_{[k+1,n]}$
and
$$\tau_1 < \cdots < \tau_{k-1} \text{ and }\tau_{k+1} < \cdots \tau_{n}$$
Note that we are restricting this factorization to the set of
$\pi$ which fix $k$, but this creates no difficulties.
Since $\sum_{\pi \in S_n} q^{inv(\pi)} = [n]!_q$, we have
$$
\sum_{\pi \in S_n} \#Fix(\pi) \,\, q^{inv(\pi)}
= \sum_{k=1}^{n} [k-1]!_q [n-k]!_q
\sum_{\tau \in S_n, \, \tau_k=k \atop
\tau_1 < \cdots \tau_{k-1}, \, \tau_{k+1} < \cdots \tau_{n}}
q^{inv(\pi)}
$$
and it only remains to compute the last sum on the right-hand side.
Given such a $\tau$, define two subsets $J_1, J_2 \subseteq [n]$ by
$$
\aligned
J_1 &= \{i: 1 \leq i \leq k-1, \,\, \tau^{-1}(i) \geq k+1 \}\\
J_2 &= \{i: k+1 \leq i \leq n, \,\,\tau^{-1}(i) \leq k-1 \}
\endaligned
$$
Note that $J_1, J_2$ must have the same cardinality which we denote
by $j$, and choosing the sets $J_1, J_2$ completely determines
$\tau$. There are exactly $j^2$ inversions between $J_1$ and $J_2$,
and exactly $2j$ inversions between $k$ and $J_1,J_2$. This accounts
for the $q^{j^2+2j}$ term in the sum. The remaining inversions of
$\tau$ come from among the numbers in $[1,k-1]$ and among the numbers
in $[k+1,n]$, and correspond to MacMahon's ``inv" statistic
on subsets \cite{Ma} applied to the sets $J_1,J_2$ respectively.
Since the distribution of ``inv" over $k$-subsets of an $n$-set is
given by $\left[ n \atop k \right]_q$, the theorem follows.
\endproof
\rem{Remark}
The last sum on the right-hand side in the preceding theorem
is similar to the {\it q-Vandermonde convolution}
$$
\sum_{j \geq 0} q^{j^2}
\left[ k-1 \atop j \right]_q
\left[ n-k \atop j \right]_q = \left[ n-1 \atop k \right]_q
$$
but does not sum so nicely. However, when we set
$q=1$ or $q=-1$, the two are the same.
%For example, setting $q=1$ in the Proposition yields
%$$
%\aligned
%\sum_{\pi \in S_n} \#Fix(\pi)
%&=\sum_{k=1}^{n}(k-1)! (n-k)!
% \sum_{j \geq 0} \left( k-1 \atop j \right)
% \left( n-k \atop j \right) \\
%&=\sum_{k=1}^{n}(k-1)! (n-k)! \left( n-1 \atop k \right) \\
%&=\sum_{k=1}^{n} (n-1)!\\
%&=n!
%\endaligned
%$$
%which is a hard way to prove an easy fact!
\endrem
Finally, we wish to prove the $s=2$ case of Conjecture 4.
Unravelling the statement in this case, it
conjectures that for all $k \leq n$, one has
$$\sum_{\pi \in S_n \atop inv(\pi) \leq k} \#Fix(\pi)
\geq \#\{\pi \in S_n: inv(\pi) \leq k\}$$
Recalling that the average permutation in $S_n$ has
one fixed point, this may be paraphrased as saying
that the set of all permutations
with length at most $k$ have, on average, ``more than
their fair share" of fixed points. This seems plausible,
since one would think that having few inversions
and having fixed points should be positively correlated.
It is not hard to see that the assertion follows from
\proclaim{Theorem \nextthm{}}
There exists a bijection $\phi$ between the sets
$$
\{(\pi,k): \pi \in S_n, \,\, k \in [n], \,\, \pi_k=k\}
\leftrightarrow S_n
$$
with the property that if
$\phi(\pi,k)=\sigma$ then $inv(\sigma) \geq inv(\pi)$.
\endproclaim
\demo{Proof}
First define the {\it folding bijection} $f:[n] \rightarrow [n]$
by
$$
f(k) = \left\{ \matrix
2 \,\,\text{min}\{k-1,n-k\}+1 &
\text{ if } k \leq \lceil {n \over 2} \rceil \\
2 \,\,\text{min}\{k-1,n-k\}+2 &
\text{ if } k > \lceil {n \over 2} \rceil
\endmatrix \right.
$$
Given a pair $(\pi,k)$ as in the left-hand side of the
theorem, define the permutation
$\sigma = \sigma_1 \sigma_2 \cdots \sigma_n$
as follows: $\sigma_1= f(k)$, and $\sigma_2, \ldots , \sigma_n$ are
the numbers $[n]-f(k)$ listed in the same relative order of magnitude
as $\pi_1, \ldots, \pi_{k-1},\pi_{k+1},\ldots \pi_n$.
It is easy to check that this is a bijection with the desired
property.
\endproof
Can such a bijection $\phi$ be found so that
$\sigma \geq \pi$ in {\it weak Bruhat order}? This would
imply that the permutations in any lower order ideal of
weak Bruhat order have, on average, ``more than their fair share"
of fixed points.
\secthead{Acknowledgements}
The authors would like to thank Paul Edelman and Dennis Stanton
for helpful discussions and references.
\Refs
\ref
\key BW
\by A. Bj\"orner and M. Wachs
\paper Generalized quotients in Coxeter groups
\jour Trans. AMS
\year 1988
\vol 308
\pages 1-37
\endref
\ref
\key Ed
\by P. H. Edelman
\paper On inversions and cycles in permutations
\jour Eur. J. Comb.
\year 1987
\vol 8
\pages 269-279
\endref
\ref
\key DF
\by J. D\'esarm\'enien and D. Foata
\paper The signed Eulerian numbers
\paperinfo preprint
\endref
\ref
\key GG
\by A. Garsia and I. Gessel
\paper Permutation statistics and partitions
\jour Adv. Math.
\year 1979
\vol 31
\pages 288-305
\endref
\ref
\key Ge
\by I. Gessel
\paper A q-analogue of the exponential formula
\jour Disc. Math.
\year 1982
\vol 40
\pages 69-80
\endref
\ref
\key GR
\by I. Gessel and C. Reutenauer
\paper Counting permutations by descent set and cycle structure
\paperinfo preprint
\endref
\ref
\key Ma
\by P. A. MacMahon
\book Combinatory Analysis, Vol .1
\publ Cambridge Univ. Press, Cambridge
\year 1915
\endref
\ref
\key Re
\by V. Reiner
\paper Descents and one-dimensional characters for
classical Weyl groups
\paperinfo to appear in Disc. Math.
\endref
\ref
\key Sa
\by B. Sagan
\book The symmetric group: representations, combinatorial algorithms,
and symmetric functions
\bookinfo Wadsworth \& Brooks/Cole
\publaddr Pacific Grove
\yr 1991
\endref
\endRefs
\end