Looking for a proof of a combinatorial relation While working on a problem, I needed to calculate the following sum
$$
n!\sum_{n_i\ge1}^{\sum_i n_i=n} 
\prod_i \frac{x_i^{n_i}}{n_i!} \tag{*}
$$
where $i$ runs from 1 to $m$. After some playing around I came to conclusion that
$$
(*)=\left(\sum_i x_i\right)^n-\sum_{\cal I_{m-1}}\left(\sum_{i\in\cal I_{m-1}}x_i\right)^n+\sum_{\cal I_{m-2}}\left(\sum_{i\in\cal I_{m-2}}x_i\right)^n - \cdots - (-1)^m \sum_{\cal I_1}\left(\sum_{i\in\cal I_1}x_i\right)^n
$$
where $\cal I_r$ are the $r$-tuples of $m$ indices. However, so far I did not succeed to prove the relation rigorously. I would be very thankful for any hint.
 A: It looks like you just want $n!$ times the coefficient of $x^n$ in 
$$ \left(\sum_{m\geq 1}\frac{x^m}{m!}\right)+\left(\sum_{m\geq 1}\frac{x^m}{m!}\right)^2+\left(\sum_{m\geq 1}\frac{x^m}{m!}\right)^3+\ldots \tag{1}$$
that is:
$$ (e^x-1)+(e^x-1)^2 + (e^x-1)^3 + \ldots  = \frac{1}{2-e^x}\tag{2}$$
so the answer depends on a Bernoulli number, since:
$$ \sum_{n\geq 0}\frac{B_n}{n!}z^n = \frac{z}{e^z-1}.\tag{3} $$
As an alternative, since
$$ \frac{1}{2-e^{x}}=\frac{1}{2}+\frac{e^{x}}{4}+\frac{e^{2x}}{8}+\ldots\tag{4} $$
we have:
$$ n! [x^n]\left(\frac{1}{2-e^{x}}\right) = \color{red}{\sum_{m\geq 1}\frac{m^n}{2^{m+1}}}\tag{5}$$
and the RHS of $(5)$ can be expressed in terms of Stirling numbers of the second kind:
$$  \sum_{m\geq 1}\frac{m^n}{2^{m+1}} = \sum_{m\geq 1}\frac{1}{2^{m+1}}\sum_{k=1}^{n}{n \brace k}k!\binom{m}{k}=\color{red}{\sum_{k=1}^{n}{n \brace k}k!}.\tag{6}$$ 
These numbers are also known as Fubini numbers or ordered Bell numbers.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{k}$ runs from $\ds{1}$ to $\ds{m}$.

\begin{align}
&\color{#f00}{\left.n!\sum_{n_{k}\ \geq\ 1} 
\prod_{k}{x_{k}^{n_{k}} \over n_{k}!}\,\right\vert_{\ \sum_{k}n_{k}\ =\ n}} =
n!\sum_{n_{k}\ \geq\ 1} 
\prod_{k}{x_{k}^{n_{k}} \over n_{k}!}\delta_{\sum_{k}n_{k}\,,\, n} =
n!\sum_{n_{k}\ \geq\ 1} 
\prod_{k}{x_{k}^{n_{k}} \over n_{k}!}\oint_{\verts{z} = 1}\,
{1 \over z^{n + 1 - \sum_{k}n_{k}}}\,{\dd z \over 2\pi\ic}
\\[5mm] = &\
n!\oint_{\verts{z} = 1}\,
{1 \over z^{n + 1}} 
\sum_{n_{k}\ \geq\ 1}\,\,\prod_{k}{\pars{x_{k}z}^{n_{k}} \over n_{k}!}
\,{\dd z \over 2\pi\ic} =
n!\oint_{\verts{z} = 1}\,
{1 \over z^{n + 1}} 
\prod_{k}\sum_{n_{k}\ \geq\ 1}\,\,{\pars{x_{k}z}^{n_{k}} \over n_{k}!}\,{\dd z \over 2\pi\ic}
\\[5mm] = &\
n!\oint_{\verts{z} = 1}\,
{1 \over z^{n + 1}} 
\prod_{k = 1}^{m}\pars{\expo{x_{k}\,z} - 1}\,{\dd z \over 2\pi\ic} =
n!\oint_{\verts{z} = 1}\,
{1 \over z^{n + 1}} 
\prod_{k = 1}^{m}x_{k}z\int_{0}^{1}\exp\pars{x_{k}\,z\,t_{k}}\,\dd t_{k}
\,{\dd z \over 2\pi\ic}
\\[5mm] = &\
n!\pars{\prod_{k = 1}^{m}x_{k}}\oint_{\verts{z = 1}}{1 \over z^{n - m + 1}}
\int_{0}^{1}\cdots\int_{0}^{1}\exp\pars{\bracks{\sum_{k = 1}^{m}x_{k}t_{k}}z}
\,{\dd z \over 2\pi\ic}\,\prod_{k = 1}^{m}\dd t_{k}
\\[5mm] = &\
n!\pars{\prod_{k = 1}^{m}x_{k}}\int_{0}^{1}\cdots\int_{0}^{1}
\sum_{j = 0}^{\infty}
{\pars{\sum_{k = 1}^{m}x_{k}t_{k}}^{\, j} \over j!}
\oint_{\verts{z = 1}}{1 \over z^{n - m - j + 1}}
\,{\dd z \over 2\pi\ic}\,\prod_{k = 1}^{m}\dd t_{k}
\\[5mm] = &\
{n! \over \pars{n - m}!}\pars{\prod_{k = 1}^{m}x_{k}}\int_{0}^{1}\cdots\int_{0}^{1}
\pars{\vec{x}\cdot\vec{t}}^{n - m}
\,\prod_{k = 1}^{m}\dd t_{k}\quad\mbox{where}\quad
\left\lbrace\begin{array}{rcl}
\ds{\vec{x}} & \ds{\equiv} & \ds{\pars{x_{1}, \ldots, x_{m}}}
\\[2mm]
\ds{\vec{t}} & \ds{\equiv} & \ds{\pars{t_{1}, \ldots, t_{m}}}
\end{array}\right.
\end{align}

Note that it $\ul{vanishes\ out}$ when $\ds{n < m}$.

A: Meanwhile I have found a rather simple proof. Let us look separately at both sides of the equation under consideration rewritten as
$$
n!\sum_{n_i\ge1}^{\sum_i n_i=n} 
\prod_i \frac{x_i^{n_i}}{n_i!} 
=\sum_{k=1}^{m}(-1)^{m-k}\sum_{I_k\in\cal I_{k}}\left(\sum_{i\in I_k}x_i\right)^n,\tag{*}
$$
where ${\cal I_{k}}$ and $I_k$ denote the set of all $k$-tuples constructed out of $m$ indices and a representative of the set, respectively.
Assuming $n\ge m $ one observes that any certain term 
$$n!\prod\frac{x_i^{n_i}}{n_i!}\tag{**}$$ 
with a fixed set of $n_i$ enters the left-hand side of (*) exactly once and only in the case when all $n_i$ are non-zero. Considering now the right-hand side of (*) one observes that the term (**) enters an expression $\left(\sum_{i\in I_k} x_i\right)^n$ at most once and this happens if and only if the tuple $I_k$ contains all indices with non-zero value of $n_i$ in (**) . Counting such tuples in every set ${\cal I}_k$ and summing them with corresponding sign $(-1)^{m-k}$ one obtains then the overall count of the term (**) on the right-hand side of expression (*). 
Assume that $l$ $n_i$'s in (**) are non-zero, so that the rest ($m-l$) ones are zero. It is easy to realize that the number of $k$-tuples containing the term is $\binom{m-l}{k-l}$. Indeed it is just the number of ways to fill $(k-l)$ "free" positions in the $k$-tuple with $(m-l)$ indices with zero value of $n_i$ in (**). Therefore the overall count of any term with $l$ non-zero $n_i$'s is:
$$
\sum_{k=l}^m(-1)^{m-k}\binom{m-l}{k-l}=(-1)^{m-l} (1-1)^{m-l}=
\begin{cases}
1,&l=m\\
0,&l<m
\end{cases},
$$
as required.
Note that if $n <m $ the equality  (*) degenerates to $0=0$.
