Let $x\_1, ..., x\_n$ be formal variables. One variant of the Newton-Girard identities expresses
$$\sum\_{\pi \in S\_n} x\_{\pi(1)} x\_{\pi(2)} \cdots x\_{\pi(k)}$$
as a polynomial in the power sums of the $x\_i$-s.


I am looking for a variant which does the following. For every $1 \le j \le m$, let $x^{(j)}\_1, ..., x^{(j)}\_n$ be formal variables. I want to express
$$\sum\_{\pi \in S\_n} x^{(1)}\_{\pi(1)} x^{(2)}\_{\pi(2)} \cdots x^{(k)}\_{\pi(k)}$$
as a polynomial in the power sums of each of the m sequences $\{ x^{(j)}\_i \}\_{i=1}^{n}$. Here I assume that $k$ is at most $m$.


Was this ever worked out previously? Or something similar to that?



A generalization of Newton-Girard Identities
Just a quick answer for now (will try to give more details later):
This is easy to do by expanding the exponential of a logarithm as in the usual symmetric function case. Basically, you are asking for an explicit formula for the multisymmetric elementary polynomials in terms of the multisymmetric power sums. You can find it, e.g., in Corollary 1.8 page 41 of [the thesis by Emmanuel Briand](https://hal.archives-ouvertes.fr/tel-00002085v1) (in french).




---


Update with the promised details:


Let $X=\left(x\_{i}^{(j)}\right)\_{i,j}$ denote the collection of indeterminates with $1\le i\le n$ and $1\le j\le m$.
Permutations $\pi\in S\_n$ act on $\mathbb{C}[X]$ via $\pi\cdot X\_{i}^{(j)}=X\_{\pi(i)}^{(j)}$. The invariant part $\mathbb{C}[X]^{S\_n}$ is the so-called *algebra of multisymmetric polynomial functions* studied in the mentioned references.


The elementary multisymmetric functions $e\_{\alpha}(X)$ or simply $e\_{\alpha}$ are defined by
$$
e\_{\alpha}=[t^{\alpha}]\ \prod\_{i=1}^{n}\left(
1+t\_1 x\_{i}^{(1)}+\cdots+t\_m x\_{i}^{(m)}\right)
$$
where $\alpha=(\alpha\_1,\ldots,\alpha\_m)\in\mathbb{N}\_{0}^{m}$ is a multiindex with $1\le |\alpha|\le n$.
I used the following standard notations: $|\alpha|=\alpha\_1+\cdots+\alpha\_m$, $t^\alpha=t\_{1}^{\alpha\_1}\cdots t\_{m}^{\alpha\_m}$, as well as $[t^{\alpha}]\cdots$ for the coefficient of the monomial $t^{\alpha}$ in the expression "$\cdots$".


Note that the OP's quantity of interest is equal to $(n-k)!\times e\_{(1,\ldots,1,0,\ldots,0)}$ where the first $k$ entries are 1's.


The multisymmetric power sums $p\_{\alpha}(X)$ or simply $p\_{\alpha}$ are defined by
$$
p\_{\alpha}=\sum\_{i=1}^{n} \left(x\_i^{(1)}\right)^{\alpha\_1}\cdots \left(x\_i^{(m)}\right)^{\alpha\_m}
$$
for any $\alpha\in\mathbb{N}\_0^{m}$.


It is known that $(p\_{\alpha})\_{1\le |\alpha|\le n}$ and also $(e\_{\alpha})\_{1\le |\alpha|\le n}$ are minimal sets of algebra generators for $\mathbb{C}[X]^{S\_n}$. These generators are not algebraically independent as in the $m=1$ case but are constrained by relations which are *very poorly understood*.
I don't think the power sums mentioned by the OP are enough to do the job because they correspond to $\alpha$'s of the form $(0,\ldots,0,r,0\ldots,0)$ with $1\le r\le n$, and that is too restrictive (see Darij's comment below for a neat argument for why this would not work).


Expressing the elementary multisymmetric functions in terms of the multisymmetric power sums can be done as follows.


$$
\prod\_{i=1}^{n}\left(
1+t\_1 x\_{i}^{(1)}+\cdots+t\_m x\_{i}^{(m)}\right)=
\exp\left[
\sum\_{i=1}^{n}\log\left(1+t\_1 x\_{i}^{(1)}+\cdots+t\_m x\_{i}^{(m)}\right)
\right]
$$
where, by the expansion of the logarithm and the multinomial theorem,
$$
\log\left(1+t\_1 x\_{i}^{(1)}+\cdots+t\_m x\_{i}^{(m)}\right)=\sum\_{p\ge 1}\frac{(-1)^{p-1}}{p}
\sum\_{\alpha\in\mathbb{N}\_{0}^{m},\ |\alpha|=p}
\left(\begin{array}{c} |\alpha| \\ \alpha \end{array}\right)
t^{\alpha} x\_{i}^{\alpha}
\ .
$$
Again I used the standard notation
$$
\left(\begin{array}{c} |\alpha| \\ \alpha \end{array}\right)
=\frac{|\alpha|!}{\alpha\_1!\cdots \alpha\_m!}
$$
and the shorthand $x\_{i}^{\alpha}=\left(x\_i^{(1)}\right)^{\alpha\_1}\cdots \left(x\_i^{(m)}\right)^{\alpha\_m}$.


Therefore,
$$
\prod\_{i=1}^{n}\left(
1+t\_1 x\_{i}^{(1)}+\cdots+t\_m x\_{i}^{(m)}\right)=
\exp\left[
\sum\_{\alpha\in\mathbb{N}\_{0}^{m},\ |\alpha|\ge 1}
\frac{(-1)^{|\alpha|-1}}{|\alpha|} 
\left(\begin{array}{c} |\alpha| \\ \alpha \end{array}\right)
t^{\alpha} p\_{\alpha}
\right]
$$


$$
=\sum\_{q\ge 0}\frac{1}{q!}\sum\_{\alpha^{(1)},\ldots,\alpha^{(q)}}
\ \prod\_{l=1}^{q}\left[
\frac{(-1)^{|\alpha^{(l)}|-1}}{|\alpha^{(l)}|} 
\left(\begin{array}{c} |\alpha^{(l)}| \\ \alpha^{(l)} \end{array}\right)\ p\_{\alpha^{(l)}}
\right]\ t^{\alpha^{(1)}+\cdots+\alpha^{(q)}}
$$
where the second sum is over all sequences of $q$ multiindices $\alpha^{(l)}\in\mathbb{N}\_0^m$ with $|\alpha^{(l)}|\ge 1$.


Finally, we get
$$
e\_{\beta}=\sum\_{q\ge 0}\frac{1}{q!}\sum\_{\alpha^{(1)},\ldots,\alpha^{(q)}}
\ \prod\_{l=1}^{q}\left[
\frac{(-1)^{|\alpha^{(l)}|-1}}{|\alpha^{(l)}|} 
\left(\begin{array}{c} |\alpha^{(l)}| \\ \alpha^{(l)} \end{array}\right)\ p\_{\alpha^{(l)}}
\right]
$$
where the sum is further restricted by the condition $\alpha^{(1)}+\cdots+\alpha^{(q)}=\beta$.


