What is the connection between sum of tuple products and permutations by cycle? 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.
 A: 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.
A: 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;

