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.
Best Answer
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$$