7
$\begingroup$

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

$\endgroup$
3
  • $\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$ Sep 21, 2011 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$ Sep 21, 2011 at 2:06
  • $\begingroup$ Ah, I got confused by the $\theta^{(n)}$. $\endgroup$ Sep 21, 2011 at 3:37

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Sep 21, 2011 at 12:57
  • $\begingroup$ Oh, got it: inversions $\neq$ involutions. Thanks for your answer! $\endgroup$ Sep 21, 2011 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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