Prove the identity $\frac{(n-1)!}{n^m}\sum_{q=1}^{\min\{m,n\}}\frac{q}{(n-q)!}\sum_{\sum_{j=1}^qa_j=m-q}\prod_{k=1}^qk^{a_k}=1-(1-\frac{1}{n})^m$ I am trying to prove the identity
$$
\dfrac{(n-1)!}{n^{m}}\sum_{i=1}^{\min\{m,n\}} \dfrac{i}{(n-i)!}\sum_{(a_1,a_2,\ldots,a_i)}\prod_{k=1}^{i} k^{a_k}=1-\left(1-\dfrac{1}{n}\right)^{m}
$$
where $m$, $n$ are positive integers, and the tuples $(a_1,\ldots,a_i)$ in the summation run over the set
$$
A_i:=\left\{(a_1,a_2,\ldots,a_i)\in\mathbf{Z}_{\geq 0}\times\cdots\times\mathbf{Z}_{\geq 0}:\sum_{j=1}^ia_j=m-i\right\}.
$$
Mathematica verifies some special cases, but the general result remains a conjecture.
 A: We seek to verify the identity
$$\frac{(n-1)!}{n^m}
\sum_{q=1}^{\min\{m,n\}} \frac{q}{(n-q)!}
\sum_{\sum_{j=1}^q a_j = m-q}
\prod_{k=1}^q k^{a_k}
= 1 - \left(1-\frac{1}{n}\right)^m$$
where the $a_j$ are non-negative integers. The inner sum is
$$\sum_{\sum_{j=1}^q a_j = m-q}
\prod_{k=1}^q k^{a_k}
= [z^{m-q}]
\prod_{k=1}^q (1+kz+k^2z^2+\cdots)
\\ = [z^{m-q}] \prod_{k=1}^q \frac{1}{1-kz}
= [z^m] \prod_{k=1}^q \frac{z}{1-kz}
= {m\brace q}.$$
We then get for the outer sum
$$\sum_{q=1}^{\min\{m,n\}} \frac{q}{(n-q)!} {m\brace q}
\\ = m! [z^m]
\sum_{q=1}^{\min\{m,n\}} \frac{1}{(n-q)! \times (q-1)!}
(\exp(z)-1)^q
\\ = \frac{m!}{(n-1)!} [z^m]
\sum_{q=1}^{\min\{m,n\}} {n-1\choose q-1} (\exp(z)-1)^q.$$
Now the binomial coefficient enforces $q\le n$ through the falling
factorial $(n-1)^{\underline{q-1}}$ and the coefficient extractor
enforces $q\le m$ because $\exp(z)-1 = z +\cdots$, taken together they
enforce $q\le\min\{m,n\}$ and we may write
$$\frac{m!}{(n-1)!} [z^m]
\sum_{q\ge 1} {n-1\choose q-1} (\exp(z)-1)^q
\\ = \frac{m!}{(n-1)!} [z^m] (\exp(z)-1)
\sum_{q\ge 0} {n-1\choose q} (\exp(z)-1)^q
\\ = \frac{m!}{(n-1)!} [z^m] (\exp(z)-1) \exp((n-1)z)
\\ = \frac{m!}{(n-1)!} [z^m] (\exp(nz) - \exp((n-1)z)).$$
Restoring the factor in front of the outer sum we obtain
$$\frac{(n-1)!}{n^m} \times
\frac{1}{(n-1)!} (n^m - (n-1)^m).$$
This is
$$\bbox[5px,border:2px solid #00A000]{
1- \left(1-\frac{1}{n}\right)^m.}$$
as claimed.
