How many ways are there to assign six different jobs to five different employees if every employee is assigned at least one job?

The answer uses the Principle of Inclusion and Exclusion and is $1800$.

And this does not agrees with my intuition.

My intuition was that to first ensure that every employee is assigned at least a job, one job must be assigned to each employee initially, which then there will be one job left.

So, $\binom{6}{5} \cdot 5!$ many ways to do it.

The one job left can then be assigned to any of the five employees.

So $5$ ways to do it.

Finally, by rule of product, there is a total of $\binom{6}{5}\cdot 5!\cdot 5 = 3600$ ways.

And this does not agree with the model answer $1800$.

Where am I thinking wrong? Any help please.

  • 3
    $\begingroup$ You are double counting. If you assign the first guy job $A$ and then later assign him job $E$ that;s the same as if you went in the other order. $\endgroup$ – lulu Sep 24 '17 at 23:28
  • $\begingroup$ I have thought of this. But when i first saw the question, this doesnt reach my mind. What should i do in general to avoid making such mistake? $\endgroup$ – Little Rookie Sep 24 '17 at 23:29
  • 2
    $\begingroup$ It can be hard. I always ask myself "what symmetries are there in the situation?" . Here, the fellow with jobs $(A,B)$ is the same as the fellow with jobs $(B,A)$. You can avoid that by working with unordered assignments or by doing exactly what you did and then dividing by $2$ to kill the symmetry. $\endgroup$ – lulu Sep 24 '17 at 23:31
  • $\begingroup$ You appear to be missing as well the crucial detail that no job has more than one employee doing it. $\endgroup$ – JMoravitz Sep 24 '17 at 23:32
  • 2
    $\begingroup$ To do it with unordered assignments: First pick the fellow with $2$ jobs ($5$ choices). then pick two jobs ($\binom 62=15$ choices), then permute the rest and assign ($4!=24$ choices). So then the answer is $5\times 15\times 24 =1800$ $\endgroup$ – lulu Sep 24 '17 at 23:34

You are counting the employee who receives two jobs twice, once for each way of designating one of his or her jobs as the job you designated as the additional job.

Notice that there are $\binom{6}{2}$ to select two jobs to give to one person. There are $5$ ways to select a person to receive those jobs and $4!$ ways to assign the remaining jobs to the remaining $4$ people. Hence, the number of permissible assignments is $$\binom{6}{2} \cdot 5 \cdot 4! = 1800$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.