In how many ways can 7 different jobs be assigned to 4 different employees so that each employee is assigned at least one job and the most difficult job is assigned to the best employee?
In the above question my approach was to first give the best employee the most difficult job,
leaving us with 6 remaining jobs. I then wanted to assure each employee gets at least one job and since the best employee already did. then the other 3 employees can select 3 jobs from the remaining 6 as follows: 6P3
but then 3 jobs are going to be remaining to be distributed so I used stars and bars method. by doing (n + k – 1)C(k – 1) which gives 6C3
so the final result that I got was (6P3) * (6C3) which is 2400.
since I saw that the correct answer should be 2100. I first want to know what is wrong with my approach, to be able to think about the other one in similar problems later on.
Best Answer
You have made two fundamental errors
To count correctly, you could use the format
[Lay down pattern ] x [Permute pattern ]
Since the hardest job has been pre-allocated to the best employee, we have only $6$ jobs to consider
$3-1-1-1: \; \dfrac{6!}{3!}\dfrac{4!}{3!}=480$
$2-2-1-1: \; \dfrac{6!}{2!2!}\dfrac{4!}{2!2!} =1080$
Since the best employee has one job, one option is to distribute the remainng jobs to only the other $3$
$4-1-1: \; \dfrac{6!}{4!}\dfrac{3!}{2!} = 90$
$3-2-1: \; \dfrac{6!}{3!2!}\cdot{3!} = 360$
$2-2-2: \; \dfrac{6!}{2!2!2!}\dfrac{3!}{3!} =90$
Ans $= 480+1080+90+360+90 =\boxed{2100}$
$\underline{\textbf{Query re stars and bars}}$
Stars and bars is used for distributing identical objects to distinct bins. Here we are distributing distinct objects (jobs) to distinct bins (people)
Also, stars and bars does not give an equiprobable distribution, which is needed if probabilities are to be computed. For example, giving all the jobs to one person would be more unlikely than a more even distribution, but for stars and bars they are all treated as identical.