# Sum over Permutations and Possible Relations with the Polya Enumeration Theorem

A specialization of the Polya enumeration theorem can give rise to the following identity:

$\frac{1}{k!} \sum_{\pi \in S_k} n^{cyc(\pi)} = {n+k-1 \choose k},$

where $S_k$ is the permutation group of degree $k$ and $cyc(\pi)$ is the number of cycles in the permutation $\pi$. Now, I am interested in the following summation

$\sum_{\pi \in S_k} n_1^{cyc(\pi)} n_2^{cyc(\pi \xi )} n_3^{cyc(\pi \xi^{-1})},$

where $\xi$ is the cyclic permutation of the cycle type $(123....k)$. Is there an expression in closed form for this summation just like the previous summation? Is this summation related to the Polya enumeration theorem in some way？ We might need to separately discuss the two cases with even $k$ and odd $k$. The naive reasoning is that, for example, if we look at the term with the highest power in, say $n_2$, we get $n_1n_2^k n_3$ for odd $k$ and $n_1n_2^k n_3^2$ for even $k$.

This is not an answer but stated here for lack of margins in the "comments" area.

First, I do not believe there will be a nice structural description for the sum, let alone a closed form. A couple of things are apparent:

(a) the sum is symmetric in $n_2$ and $n_3$ but not in $n_1$;

(b) while from above, $$\sum_{\pi\in S_k}x^{cyc(\pi)}=(x)^{(k)}.$$ Here is a contrasting analogue $$-\sum_{\pi\in S_k}x^{cyc(\pi)}(-1)^{cyc(\pi\xi)}=(x)_{(k)}.$$

Notations. $(x)^{(k)}$ and $(x)_{(k)}$ stand for rising and falling factorials, respectively.

• Thank you for your comment. I am quite curious about the second identity you wrote here. Could you please explain a bit how to derive it? – Chao-Ming Jian Sep 26 '16 at 1:38
• If $k$ is odd and $\pi\in S_k$ then $cyc(\pi)$ and $cyc(\pi\xi)$ have the same parity. If $k$ is even and $\pi\in S_k$ then $cyc(\pi)$ and $cyc(\pi\xi)$ have opposite parity. – T. Amdeberhan Sep 26 '16 at 4:48