Could someone explain why $\sum_{\substack{a_1,\ldots,a_n\in\mathbb{N}_0\\a_1+\cdots+a_n=n}}\frac{n!}{a_1!\cdots a_n!}=n^n$?

Question

I want to use this equality but I have no idea why it holds. Sure I can probably prove it via induction but it looks rather fiddly. (Let $n$ be a positive integer.)

$$\sum_{\substack{a_1,\ldots,a_n\in\mathbb{N}_0\\a_1+\cdots+a_n=n}}\frac{n!}{a_1!\cdots a_n!}=n^n$$

Is there a simpler way/intuition to explain this equality? It looks like something from combinatorics/probability but I cannot exactly recall what.

Thank you so much in advance!

Edit: This arise from a homework problem where I am asked to look at the probability of arranging $n$ objects where there are indistinguishable items, $a_1$ number of first item etc and hence the expression in the sum. I wanted to sum up every possibility and thus I was curious why it would sum up to $n^n$. (It sums up to $n^n$, which was given in the original question but I wanted to know why.)

Answer 1

Consider $(x_1 + x_2 + \dots + x_n)^n$, use multinomial theorem and put $x_i = 1$.

Answer 2

Suppose you want to distribute the set $\{1, \dots, n\}$ over $n$ sets $A_1, \dots, A_n,$ where you put $a_1$ elements in $A_1,$ $a_2$ elements in $A_2$ and so on. The amount of possibilities to do so is exactly $\frac{n!}{a_1!\cdots a_n!}.$ Now you sum over the number of such distributions for every possible tuple of cardinalities, so what you end up with is just the number of possibilities to distribute $\{1, \dots, n\}$ over $n$ sets. And this is $n^n,$ as for each element you have $n$ possible sets to put it into.

This is also how you see that the multinomial formula holds, which is $$ (x_1 + \dots + x_n)^n = \sum_{a_1 + \dots + a_n = n} \frac{n!}{a_1!\cdots a_n!}{x_1}^{a_1} \dots {x_n}^{a_n}.$$ This shows you claim after setting $x_1 = \dots = x_n = 1.$