How to prove multinomial partitioning

Question

I was assigned an extra problem by my instructor (who's a grad student btw). So far, I know this question requires combinations and summation but I am so lost - I have no idea how to go about writing it or even starting it.

A picture of the question

Here's my current understanding of the problem: I have n items, and I want to put them into k subsets (where k^n) requires the use of the multinomial theorem.

Thanks and I appreciate any help or hints!!

Answer 1

I guess you refer to the multinomial theorem:

$$(x_1+\ldots+x_k)^n = \sum_{n_1+\ldots+n_k=n} {n\choose n_1,\ldots,n_k} x_1^{n_1}\cdots x_k^{n_k}.$$

Put $x_1=\ldots=x_k=1$.