X people line up to get into Y different clubs.

Question

I have a combinatorics problem, and I don't know my answer is correct or not.

The problem is the following :

Assume that X people line up to get into Y different clubs. How many ways are there to do it? (The people are distinguishable and the order people are in line matters.)

My attempt : we have Y different kinds of clubs. So, we have ${X+Y-1 \choose X}$. But, $X$ people are distinguishable, we have to permute them, $X!$. Thus, the final answer is $X!{X+Y-1 \choose X}$. Is that right answer?

Answer 1

I was initially skeptical of your answer, but eventually I arrived at the same thing. I got there from the other direction, though.

First, set aside the clubs for a moment. There are $X!$ ways to arrange the punters in a single queue. Now take one of those arrangements. We need to apportion them so that in front of one club there's one, maybe; in front of another, there are none; in front of a third, there are three; etc. Basically, we have $X$ indistinguishable — right? we've fixed our arrangement for the moment — people to distribute among $Y$ distinguishable containers, and this can be done $\left(\!\!\left(Y\atop X\right)\!\!\right) = \binom{Y+X-1}{X}$ ways.

So we can line everyone up $X!\binom{Y+X-1}{X}$ ways.

Answer 2

Lets consider a specific example:

We have three people: Alan, Bob and Chris We have four Clubs Disco Stu's, Eddie's Bar, Flamingo's and Gary's Gogo.

Now if we assume each person is free to choose which club they go to and they choose in the order given

Alan, Bob and Chris each have a choice of 4 clubs so that's $4 \times 4 \times 4 =64 $ ways they can choose but we care about the order so how many ways can you order 3 people.

Making Any of 3 people can choose first any of the remaining two can choose next and finally there is only one person left to choose making $3 \times 2 \times 1 = 6$ ways So we have $6 \times 64 = 384 $ possible ways to solve this

Extracting this to the general case with $ x $ people and $ y $ clubs we have:

$$x! \cdot y^x$$

Possible ways to choose, if we care about order and who goes where.