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$?

  • $\begingroup$ 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? $\endgroup$ – darij grinberg Sep 21 '11 at 1:49
  • $\begingroup$ @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$... $\endgroup$ – Gjergji Zaimi Sep 21 '11 at 2:06
  • $\begingroup$ Ah, I got confused by the $\theta^{(n)}$. $\endgroup$ – darij grinberg Sep 21 '11 at 3:37

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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