MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

By the Bruhat decomposition of $GL(n, \mathbb{F}_q) / B_n$ we know that $$[n]! = \sum_{ \sigma \in S(n)} q^{l(\sigma)}$$ where $[n]! = \prod_{j=1}^n (1+q + \cdots + q^{j-1})$ and $l(\sigma)$ is the length of the permutation $\sigma \in S(n)$ (also known as the number of involutions of $\sigma$).

We also know that $$\theta^{(n)} = \sum_{\sigma \in S(n)} \theta^{[\sigma]}$$ where $[\sigma]$ is the number of cycles of the permutation $\sigma \in S(n)$ and $\theta^{(n)} = \theta(\theta+1) \cdots (\theta+n-1)$. Notice that $$\lim_{q \rightarrow 1} \ [n]! = n! = \lim_{\theta \rightarrow 1} \ \theta^{(n)}.$$ Is there a way to write $$\sum_{\sigma \in S(n)} q^{l (\sigma)} \theta^{[\sigma]}$$ explicitly as a function of $q$ and $\theta$?

share|cite|improve this question
For $n=3$, I am getting $\theta(\theta+1)(\theta+2)+\theta(\theta+1)(q+q+q^3)+\theta(q^2+q^2)$. This does not factor further than $\theta\cdot ...$. Am I understanding the problem correctly? – darij grinberg Sep 21 '11 at 1:49
@darij, I get $\theta^3+\theta^2(2q+q^3)+2\theta q^2$. when $\theta=q=1$ the expression should reduce to $n!$, yours gives $14$... – Gjergji Zaimi Sep 21 '11 at 2:06
Ah, I got confused by the $\theta^{(n)}$. – darij grinberg Sep 21 '11 at 3:37
up vote 7 down vote accepted

It seems like there is no hope for a nice closed form for $F(q,\theta)=\sum_{\sigma\in S_n}q^{l(\sigma)}\theta^{[\sigma]}$. When the sum is restricted to $\sigma\in S_n$ which are involutions, the computation can be found in I. Gessel's paper "A q-analog of the exponential formula".

For the general case, the study of $F(q,\theta)$ is the main topic of P.H. Edelman's paper "On inversions and cycles in permutations" (Europ. J. Combinatorics,(1987) vol 8, 269-279). he proves a bunch of properties of this bivariate generating function, yet, according to this paper even computing the number of permutations which achieve the minimum number of cycles with a fixed number of inversions hasn't been carried. It gives a bunch of open problems about $F(q,\theta)$.

If on the other hand you let $l(\sigma)$ denote the number of inversions of $\sigma$ written in cycle notation (i.e. the number of inversions in $(a_1\dots a_{k_1})(a_{k_1+1}\dots a_{k_2})\cdots(a_{k_{r}+1}\dots k_{r+1})$) then the sum is $\prod _{i=1}^n [i] _{q} ^{\theta}$, where $$[i]_{q}^{\theta}= 1+q+\cdots+q^{i-2}+\theta q^{i-1}.$$ This is proved in "Cycles and patterns in permutations" by R. Parviainen.

share|cite|improve this answer
Could you clarify the difference between the definition of $l(\sigma)$ above and "the number of inversions of $\sigma$ written in cycle notation"? – Alexander Moll Sep 21 '11 at 12:57
Oh, got it: inversions $\neq$ involutions. Thanks for your answer! – Alexander Moll Sep 21 '11 at 13:00

Your Answer


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.