TITLE: Is there a closed form solution for the following recurrence relation?
QUESTION [2 upvotes]: As I was trying to solve a problem dealing with some discrete probabilities I had to evaluate 
$$ y(m) = \sum_{\substack {k_1 + ... + k_m = n \\ k_1 \geqslant 1, ..., k_m \geqslant 1}} \binom{n}{k_1, ..., k_m}, $$ here $n$ is a constant and $n \geqslant m$
. This lead me to solving the following non-trivial recurrence relation:
$$ y(m) + \sum_{k = 1}^{m - 1} \binom{m}{k}y(m - k) = m^n, \\
y(1) = 1$$.
I would like to know whether it's possible to express $y(m)$ in a closed form?

REPLY [2 votes]: Your $y(m)$ is the number of ways to put $n$ distinguishable balls in $m$ distinguishable boxes, with $\geq 1$ ball per box.  This is almost the same as the Stirling number of the second kind $S(n,m)$, which is the number of ways to put $n$ distinguishable balls in $m$ indistinguishable boxes.  The distinguishability of your boxes means that your $y(m)=m!S(n,m)$, since there are $m!$ ways to arrange the boxes. 
There is not a totally closed form solution for $S(m,n)$, but there are explicit formulas, for example $$S(n,m) = \frac{1}{m!}\sum_k (-1)^{m-k} \binom{m}{k}k^n$$
Hence your $y(m)$ can be expressed as $y(m) = \sum_k (-1)^{m-k} \binom{m}{k}k^n$.
You can reach the same formula by inclusion-exclusion: The number of ways to put the $n$ balls into $m$ boxes without regard to the $\geq 1$ ball per box condition is $m^n$.  The number of ways to put the balls in some $m-k$ boxes is $\binom{m}{k}(m-k)^n$, and applying inclusion-exclusion to determine the number of configurations that are NOT contained in some $m-1$ boxes (meaning each box has at least one ball) gives $$y(m) = m^n+\sum_k (-1)^k\binom{m}{k}(m-k)^n = \sum_k (-1)^{m-k} \binom{m}{k} k^n$$
as above.
{"set_name": "stack_exchange", "score": 2, "question_id": 2569700}