3
$\begingroup$

This question is inspired but not directly related to this recent Stanley's MO post.

The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ (the symmetric group on $\{1,\dots,n\}$) is defined by $D(w)=\{ 1\leq i\leq n-1\,:\, a_i>a_{i+1}\}$. Denote the cardinality of $D(w)$ by $des(w)$.

The Eulerian polynomials are known to express $$A_n(x)=\sum_{w\in\frak{S}_n}x^{des(w)}$$ whose exponential generating function is given by $$\sum_{n\geq0}A_n(x)\,\frac{z^n}{n!}=\frac{1-z}{z-e^{(1-z)x}}.$$ Suppose we wish to refine this by including the cycle-type of each permutation.

QUESTION. Is there a generating function for the sum $$\sum_{w\in\frak{S}_n}x^{des(w)}\,t_1^{a_1}t_2^{a_2}\cdots t_n^{a_n}$$ where $(a_1,\dots,a_n)$ is the cycle-type of $w$? Caveat. the $a_i$'s are non-negative integers.

Examples. The first few polynomials for $n=1, 2, 3$ and $4$: \begin{align*} &t_1 \\ &t_1^2+t_2x \\ &t_1^3+(2t_1t_2+2t_3)x+t_1t_2x^2 \\ &t_1^4+(3t_1^2t_2+4t_1t_3+t_2^2+3t_4)x+(3t_1^2t_2+4t_1t_3+t_2^2+3t_4)x^2+t_2^2x^3. \end{align*}

$\endgroup$
1
  • $\begingroup$ Close to what you want: the number of permutations with descent set $S\subseteq [n-1]$ and cycle type $\lambda$ is $\langle L_{\lambda}, s_{B_S}\rangle$ where $s_{B_S}$ is the ribbon Schur function and $L_{\lambda}$ is the Lyndon symmetric function. See Stanley's recent slides: math.mit.edu/~rstan/transparencies/permenum.pdf. $\endgroup$ Apr 7, 2022 at 23:10

1 Answer 1

9
$\begingroup$

Counting permutations by cycle type and descents was first accomplished in I. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64, No. 2 (1993), 189–215.

Using the results of this paper, an explicit (though somewhat complicated) formula for the generating function asked for can be found in Jason Fulman, The distribution of descents in fixed conjugacy classes of the symmetric groups, J. Combin. Theory Ser. A 84 (1998), no. 2, 171–180. Another proof of Fulman's formula is Theorem 7.1 (c) in Ira M. Gessel and Yan Zhuang, Plethystic formulas for permutation enumeration, Adv. Math. 375 (2020), 107370, 55 pp.

$\endgroup$
1
  • $\begingroup$ Thank you for this, Ira. $\endgroup$ Apr 9, 2022 at 16:21

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.