# How many different lists can be made.

There are $n$ workers in a factory and $k$ entrances to it. In each entrance, a worker has to sign up on a list in order to enter. I have to find out two things:

a) How many different lists can be made? (order matters)

b) How many ways can you divide workers into lists so that each list is non-empty?

Here's my solution:

a) We choose one of the $n$ workers and be put them on one of the $k$ lists, then we choose one of $n-1$ workers and do the same, etc. In the end the answer is $n!k^n$.

b) Basically, we have to find out all solutions to $x_{1}+x_{2}+...+x_{k}=n$ where each $x_{i} \neq 0$. There are ${{n-1}\choose{k-1}}$ way to do that. But we have to put a worker into each of the spots we have separated, and we do that $n!$ different ways, so in the end the answer is $n!{{n-1}\choose{k-1}}$.

Is this correct?

-
For a) your solution is wrong, since unless the first two workers enter by the same entrance, you cannot tell from the lists which one was chosen first. For b) the question is not very clear. Does "divide workers" imply that now the order on each list does not matter any more? And maybe permuting the lists among each other is not considered to give a different partition? If order still matters, the difference between a) and b) is only the non-empty requirement. – Marc van Leeuwen Nov 2 '13 at 12:32
b) is a special case of a), in which all of the lists are non-empty. So how to solve a? I have trouble imagining it. It seems we still have an equation $x_{1}+x_{2}+...+x_{k}=n$, but some $x_{i}$ could be equal $0$. But how to take order into account? There are ${n+k-1}\choose{k}$ solutions, and then there are $n!$ ways we could fit all the workers into them, so the answer is $n!{n+k-1}\choose{k}$, right? – Arek Krawczyk Nov 2 '13 at 12:38
Correction, $n!{{n+k-1}\choose{k}}$, my Latex skills failed me and I can't edit my comment above. – Arek Krawczyk Nov 2 '13 at 12:49

Case a): For $k$ doors, place $k-1$ door-openers in the queue. The $n+k-1$ people can be arranged in $(n+k-1)!$ ways, but the door-openers are indistinguishable, so the total of different lists is $(n+k-1)!/(k-1)!=n!{n+k-1\choose k-1}$
In case b): Give a doorkey to the first worker, and to $k-1$ of the other workers, so the answer is $n!{n-1\choose k-1}$ different ways.

-

One way to see problem $b$ is to first selecting one worker per entrance, which can be made in ${}^nP_k=\frac{n!}{(n-k)!}$ ways, then you have $n-k$ workers to be listed en $k$ lists, which is the same as case a).

So first order your $n$ or $n-k$ worker ($n!$ in the first problem) and then divide that list in $k$ sublists. Take rather the spaces between workers including the space before any worker and the space after all workers ($n+1$) and choose $k-1$ of them as list separators: you get ${}^{n+1}C_{k-1}=\binom{n+1}{k-1}=\frac{(n+1)!}{(k-1)!(n-k+2)!}$.

a) $n!\binom{n+1}{k-1}$

b) ...

-