Assume that there are $n$ people line up to get into $m$ different clubs. How many ways to do it if each people is different and order of people in the line matters.
Sol. Clearly, each people has $m$ different choices for clubs. So there are $m^n$ ways of choosing clubs. Now we count number of different lines. Let $x_i$ be the number of people lining to get to the club $i$, $1 \leq i \leq m$, $x_i \geq 0$.
Then $$x_1 + x_2 + ... + x_m = n$$ with $x_i$ non-negative integers. So there are ${m+n-1}\choose{n-1}$ ways, ignore order in each line. So there are ${m+n-1}\choose{n-1}$$ x_1!x_2!...x_n!$ possible lines.
The answer is weird since it is in $x_1, ...,x_n$ terms, and I think it is wrong. However, I am not sure how to fix it.
Any help please ?
First, there are $n!$ ways to order all people. For each of these ways, there are ${m+n-1 \choose n-1}$ ways to break up that ordering into $m$ clubs (using stars and bars), thus there is a total of $n!{m+n-1 \choose n-1}$ ways.