What is the connection between sum of tuple products and permutations by cycle?

Question

From my previous question Disjoint sets in a combinatoral sum (continued), let $X = \{x_1, \dots, x_n\}$ be a set and $$f_X(m) = \sum_{X' \in \binom{X}{m}} \prod_{x \in X'} x$$

Let $S_k = \sum x_i^k$. We can calculate with inclusion-exclusion:

$$f_X(2) = \frac{1}{2!} (S_1^2 - S_2)$$

$$f_X(3) = \frac{1}{3!} (S_1^3 - 3 S_2 S_1 + 2 S_3) $$

and so on.

In the previous answer I discovered a connection between permutations by cycle type and the coefficients of the expression $f_X(m)$ (table at https://oeis.org/A181897), and came up with a tenuous explanation. Can someone confirm my answer and elucidate if my reasoning is correct? Also what is the connection to integer partitions? I am not that experienced with combinatorics or group theory so an answer that is as elementary as possible (possibly at the expense of generality) is appreciated. I'm looking for references to this problem which has surely been explored in the past.

Answer 1

This is very classical material, closely related to Newton's identities for the elementary and the power sum symmetric functions; that keyword will bring up a lot of references. I like Chapter 7 of Stanley's Enumerative Combinatorics, Vol. II but be warned that it has a lot of material.

Here is a short but maybe unsatisfying proof. Your functions $f_m$ are more commonly known as the elementary symmetric functions and denoted $e_m$. Your functions $S_k$ are more commonly known as the power sum symmetric functions and denoted $p_k$. The elementary symmetric functions have generating function

$$E(t) = \sum_{k=0}^n e_k t^k = \prod_{i=1}^n (1 + tx_i)$$

whereas the power sum symmetric functions have generating function

$$P(t) = \sum_{k=0}^{\infty} p_k t^k = \sum_{i=1}^n \frac{1}{1 - tx_i}.$$

These generating functions can be related by the logarithmic derivative, which gives

$$\log E(t) = \sum_{i=1}^n \log (1 + tx_i)$$

and hence

$$\frac{d}{dt} \log E(t) = \sum_{i=1}^n \frac{x_i}{1 + tx_i} = \sum_{k=0}^{\infty} (-1)^k p_{k+1} t^k.$$

Integrating both sides gives

$$\log E(t) = \sum_{k=1}^{\infty} (-1)^{k-1} \frac{p_k}{k} t^k$$

and exponentiating gives

$$E(t) = \exp \left( \sum_{k=1}^{\infty} (-1)^{k-1} \frac{p_k}{k} t^k \right).$$

Expanding this out completely gives an identity relating $e_k$ and $p_k$ in terms of sums over permutations, generalizing the ones you gave, by the permutation form of the exponential formula. It can be stated succinctly as follows: if $\sigma \in S_n$ is a permutation, write $\text{sgn}(\sigma)$ for its signature, and write $p_{\sigma} = \prod_{i=1}^n p_i^{c_i(\sigma)}$ where $c_i(\sigma)$ is the number of $i$-cycles of $\sigma$. Then

$$\boxed{ e_n = \frac{1}{n!} \sum_{\sigma \in S_n} \text{sgn}(\sigma) p_{\sigma} }.$$

Some years ago I tried to work out a purely combinatorial proof of an equivalent version of this identity involving the complete homogeneous symmetric polynomials $h_k$, namely

$$h_n = \frac{1}{n!} \sum_{\sigma \in S_n} p_{\sigma}$$

which is equivalent to the previous one via the substitution $t \mapsto -t$ in the generating function. You can see how far I got in my blog post Newton's sums, necklace congruences, and Zeta functions II; there it's stated somewhat indirectly in terms of walks on graphs (the $x_i$ correspond to the eigenvalues of the graph) and it could be cleaned up to work in terms of the $x_i$ directly. I haven't tried to push through an argument for the $e_k$ version involving inclusion-exclusion but I wouldn't be surprised if it was possible. The $h_k$ version of the identity is, I think, a special case of the Polya enumeration theorem.

Answer 2

To find a closed form for $f_X(m)$ in terms of the $S_\ell$ we first require the exponential formula for the cycle index of the unlabeled set operator

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}.$$

Let $A$ be a generating function in some number of variables and let $B = c_B X_B$ a contributing monomial term where $c_B$ is the leading coefficient (positive) and $X_B$ the product of the variables to their respective powers, so that $A= \sum_{B\in A} c_B X_B$. We then have from first principles that the generating function of sets drawn from $A$ containing $m$ elements is

$$[z^m] \prod_{B\in A} (1 + z X_B)^{c_B}.$$

Manipulate this to obtain

$$[z^m] \prod_{B\in A} \exp \log (1 + z X_B)^{c_B} \\ = [z^m] \prod_{B\in A} \exp \left(- c_B \log \frac{1}{1 + z X_B} \right) \\ = [z^m] \exp \sum_{B\in A} \left(- c_B \log \frac{1}{1 + z X_B} \right) \\ = [z^m] \exp \sum_{B\in A} \left(- c_B \sum_{\ell\ge 1} (-1)^\ell X_B^\ell \frac{z^\ell}{\ell} \right) \\ = [z^m] \exp \left( \sum_{\ell\ge 1} (-1)^{\ell-1} \left(\sum_{B\in A} c_B X_B^\ell\right) \frac{z^\ell}{\ell} \right).$$

But $\sum_{B\in A} c_B X_B^\ell$ is by definition the Polya substitution applied to $A$ through the cycle index variable $a_\ell$ and we have proved the exponential formula for the unlabeled set operator, which says that

$$Z(P_m) = [z^m] \exp \left(\sum_{\ell\ge 1} (-1)^{\ell-1} a_\ell \frac{z^\ell}{\ell}\right).$$

Now we have from the definition applying PET that

$$f_X(m) = Z(P_m; x_1+x_2+\cdots+x_n).$$

Hence

$$f_X(m) = [z^m] \exp \left(\sum_{\ell\ge 1} (-1)^{\ell-1} S_\ell \frac{z^\ell}{\ell}\right) \\ = [z^m] \prod_{\ell\ge 1} \exp \left( (-1)^{\ell-1} S_\ell \frac{z^\ell}{\ell}\right) \\ = [z^m] \prod_{\ell\ge 1} \sum_{q\ge 0} \frac{1}{q!} (-1)^{q(\ell-1)} S_\ell^q \frac{z^{\ell q}}{\ell^q}.$$

We want to expand this product. We are interested in the coefficient on $[z^m]$ so we consider integer partitions $\lambda\vdash m$. Let the partition be $1^{q_1} 2^{q_2} 3^{q_3} \cdots$ where all but a finite number of exponents are zero. We now obtain

$$[z^m] \sum_{\lambda\vdash m} \prod_{\ell\ge 1} \frac{1}{q_\ell!} (-1)^{(\ell-1)q_\ell} S_\ell^{q_\ell} \frac{z^{\ell q_\ell}}{\ell^{q_\ell}}.$$

Since $\sum_{\ell\ge 1} \ell q_\ell = m$ this becomes

$$\sum_{\lambda\vdash m} \prod_{\ell\ge 1} \frac{1}{q_\ell!} (-1)^{(\ell-1)q_\ell} S_\ell^{q_\ell} \frac{1}{\ell^{q_\ell}} \\ = (-1)^m \sum_{\lambda\vdash m} (-1)^{\sum_{\ell\ge 1} q_\ell} \prod_{\ell\ge 1} S_\ell^{q_\ell} \frac{1}{q_\ell! \times \ell^{q_\ell}}.$$

We thus get the closed form

$$\bbox[5px,border:2px solid #00A000]{ f_X(m) = \frac{(-1)^m}{m!} \sum_{\lambda\vdash m} (-1)^{\sum_{\ell\ge 1} q_\ell} \left(\prod_{\ell\ge 1} S_\ell^{q_\ell} \right) \left(m! \prod_{\ell\ge 1} \frac{1}{q_\ell! \times \ell^{q_\ell}}\right).}$$

This yields for example

$$f_X(4) = \frac{1}{4!} \left({S_{{1}}}^{4}-6\,{S_{{1}}}^{2}S_{{2}} +8\,S_{{1}}S_{{3}}+3\,{S_{{2}}}^{2}-6\,S_{{4}}\right)$$

and

$$f_X(5) = \frac{1}{5!} \left({S_{{1}}}^{5}-10\,{S_{{1}}}^{3}S_{{2}}+20\,{S_{{1}}}^{2}S_{{3}} +15\,S_{{1}}{S_{{2}}}^{2}-30\,S_{{1}}S_{{4}} -20\,S_{{2}}S_{{3}}+24\,S_{{5}}\right).$$

We now show that

$$m! \prod_{\ell\ge 1} \frac{1}{q_\ell! \times \ell^{q_\ell}}$$

counts the number of permutations with cycle structure $\lambda.$

First, selecting the values to go on the cycles yields the multinomial coefficient

$$\frac{m!}{\prod_{\ell\ge 1} (\ell!)^{q_\ell}}.$$

A set of $\ell$ values gives $\frac{\ell!}{\ell}$ cycles:

$$\prod_{\ell\ge 1} \left( \frac{\ell!}{\ell} \right)^{q_\ell}.$$

Any permutation of the cycles of length $\ell$ yields the same permutation:

$$\prod_{\ell\ge 1} \frac{1}{q_\ell!}.$$

Multiply these to obtain

$$\frac{m!}{\prod_{\ell\ge 1} (\ell!)^{q_\ell}} \prod_{\ell\ge 1} \left( \frac{\ell!}{\ell} \right)^{q_\ell} \prod_{\ell\ge 1} \frac{1}{q_\ell!} = m! \prod_{\ell\ge 1} \frac{1}{q_\ell! \times\ell^{q_\ell}}.$$

This is the claim and concludes the argument.

As an addendum we have by inspection for the boxed closed form that it is given by a substitution into $Z(Q_m)$, the cycle index of the symmetric group (the variable $S$ is in use already), which is

$$Z(Q_m; a_\ell = (-1)^{\ell -1} S_\ell).$$

With $Z(Q_m)$ being the average of all $m!$ permutations factorized into cycles, where $a_\ell$ stands for a cycle of $\ell$ elements we have

$$Z(Q_m) = \frac{1}{m!} \sum_{\lambda\vdash m} \left(\prod_{\ell\ge 1} a_\ell^{q_\ell} \right) \left(m! \prod_{\ell\ge 1} \frac{1}{q_\ell! \times \ell^{q_\ell}}\right).$$

Now put $a_\ell = (-1)^{\ell-1} S_\ell$ to get the boxed form. The substitution $a_\ell := (-1)^{\ell-1} a_\ell$ converts the unlabeled multiset operator into the unlabeled set operator through their cycle indices.

There is also some Maple code for the curious who would want to study these polynomials and verify the correctness of the closed form.

with(combinat);

fX1 :=
proc(m, n)
local t;

    coeff(expand(mul(1+u*x[t], t=1..n)), u, m);
end;

fX2 :=
proc(m)
    local res, part, mset, ent;

    res := 0;

    part :=  firstpart(m);

    while type(part, list) do
        mset := convert(part, `multiset`);

        res := res +
        (-1)^add(ent[2], ent in mset)
        * mul(S[ent[1]]^ent[2], ent in mset)
        * m!/mul(ent[2]!*ent[1]^ent[2], ent in mset);

        part := nextpart(part);
    od;

    res*(-1)^m/m!;
end;

fX :=
proc(m, n)
local l, sl, t;

    sl := [seq(S[l] = add(x[t]^l, t=1..n), l=1..m)];
    expand(subs(sl, fX2(m)));
end;

pet_cycleind_symm :=
proc(n)
local l;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

fX2A :=
proc(m)
local sl, l;

    sl := [seq(a[l] = (-1)^(l-1) * S[l], l=1..m)];
    subs(sl, pet_cycleind_symm(m));
end;