The answer to a particular calculation in quantum information theory gives me the following expression:

Given $M$ specific elements of the symmetric group $S_n$, define the polynomial

$$Z_n(\pi_1, \dots , \pi_M ; X_i) = \sum_{\pi \in S_n} X_1^{C(\pi \cdot \pi_1)} X_2^{C(\pi \cdot \pi_2)} \cdots X_M^{C(\pi \cdot \pi_M)}$$

where $C(\pi)$ counts the number of disjoint cycles in the permutation $\pi$.

For $M=1$, this is related to the ordinary cycle index $Z(S_n; a_1, a_2, \dots)$ by

$$Z_n(\pi_1;X) = n! Z(S_n ; X,X, \dots)$$

My question is whether there is some useful discussion of this object $Z_n$ in the literature, or whether anyone can recommend an approach for calculating $Z_n$ for specific elements $(\pi_1,\dots, \pi_M)$ (a simple example of interest would be $\pi_1$ equal to the identity and $\pi_2$ equal to a cyclic permutation).


For $M=2$ we get a "solution" as follows. For given $\pi_1$ and $\pi_2$ we want to know how many permutations $\pi$ are there such that $\pi\pi_1$ has $c_1$ cycles and $\pi\pi_2$ has $c_2$ cycles. Let $\rho_1=\pi\pi_1$ and $\rho_2=\pi\pi_2$.

Writing $\pi\pi_2=\pi\pi_1\pi_1^{-1}\pi_2=\rho_1\pi_1^{-1}\pi_2=\rho_2$, we arrive at a factorization problem: Given $\pi_1^{-1}\pi_2$, find in how many ways it can be written as a product $\rho_1^{-1}\rho_2$ such that $\rho_1$ has $c_1$ cycles and $\rho_2$ has $c_2$ cycles.

Such quantities are related to connection coefficients of the symmetric group, and can be computed in terms of characters. There is a large literature on factorization problems, but simple explicit formulas are not easy to come by.

You can find somre references here: G. Berkolaiko, J. Irving, Inequivalent Factorizations of Permutations, http://arxiv.org/abs/1405.5255.

For general $M$ we can take $\pi_1$ and insert it in the other equations, arriving at $M-1$ simultaneous factorizations, $$\pi_1^{-1}\pi_i=\rho_1^{-1}\rho_i,\quad 2\le i\le M.$$ The problem here is that the first factor is common to all of them, so they are coupled. I have never seen anything about this.


For $M=2$, the following can be shown using the case $k=3$ of Exercise 7.70 in Enumerative Combinatorics, vol. 2. I use notation from this reference. We may assume that $\pi_1$ is the identity permutation. Suppose that $\pi_2$ has cycle type $\lambda$. Write $$ F_\lambda(x,y) = Z_n(\mathrm{id},\pi_2;x,y). $$ Define the symmetric function $$ G_n = \sum_{\lambda\vdash n}\frac{n!}{z_\lambda}F_\lambda(x,y)p_\lambda. $$ For instance, $$ G_3 = (x^3y^3+3x^2y^2+2xy)p_1^3 + 3(x^3y^2+x^2y^3+2x^2y+2xy^2)p_2p_1 + 2(x^3y+xy^3+3x^2y^2+xy)p_3. $$ Then $$ G_n = \sum_{\lambda\vdash n} f^\lambda \prod_{u\in\lambda}(x+c(u))(y+c(u))\cdot s_\lambda. $$ To extract the coefficient of $p_\mu$ from $G_n$, use $$ s_\lambda =\sum_{\mu\vdash n}z_\lambda^{-1} \chi^\lambda(\mu) p_\mu. $$ This gives an explicit formula for $F_\lambda(x,y)$, but it is not so elegant since it involves irreducible character values of $S_n$.


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.