Question 44
Let $m$, $n$ be positive integers with $m \ge n$, and let $S$ be the set of all ordered $n$-tuples $(a_1, a_2, \dots, a_n)$ of positive integers such that $a_1 + a_2 + \dots + a_n = m$. Show that
$$
\sum_{S} 1^{a_1} 2^{a_2} \cdots n^{a_n} = \binom{n}{n} n^m - \binom{n}{n-1} (n-1)^m + \cdots + (-1)^{n-2} \binom{n}{2} 2^m + \cdots + (-1)^{n-1} \binom{n}{1}.
$$
$$
\sum_{S} 1^{a_1} 2^{a_2} \cdots n^{a_n} = \binom{n}{n} n^m - \binom{n}{n-1} (n-1)^m + \cdots + (-1)^{n-2} \binom{n}{2} 2^m + \cdots + (-1)^{n-1} \binom{n}{1}.
$$