permutation combo

Question

In how many ways can seven 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?

Comments

Answer 1512 ??

---

what is given ans??

---

2100 is the answer

Answer 1

7 jobs to be given to 4 employees and each one must get at least 1 job. But the most difficult one goes to the best employee. So, the problem reduces to

1. Giving 6 jobs to 3 employees such that each one gets 1 job (here best employee gets exactly 1 job which is the toughest)
2. Giving 6 jobs to 4 employees such that each one gets 1 job (here best employee gets at least 2 jobs).

Now, 1 is same as putting 6 identical balls to 3 distinct bins such that no bin is empty and is  given by $3! \times S(6,3)=90*6 = 540$ and similarly 2 is given by $4!*S(6,4)=65*24 = 1560$. So, total ways = $540+1560=2100$. $S(m,n)$ is Stirlings number of second kind and can be derived using the triangle given below,

$S(m,n) = S(m-1,n-1) + nS(m-1, n), m,n > 1$

$S(m,1) = S(m,m) = 1$

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1

Comments

Just an observation

Stirling number of second kind with the restriction that every box must have atleast one ball is similar to surjection :)

---

Now, 1 is same as putting 6 identical balls to 3 distinct bins such that no bin is empty

Shouldn't it be 6 distinct balls to 3 distinct bins such that no bin is empty?

---

@Arjun Sir One thing I don’t get is that Why don’t you take no of ways to choose the best employee?

 There should be 4 ways of doing this.

Answer 2

Taking the same cases as Arjun sir did

But I don't use stirling number

Let J1 be the most difficult job and E1 is the best employee

 

Case 1-J1 is assigned to E1. Now E1 wont be assigned any other job

So the remaining jobs J2-J7 will be assigned among E2-E4

Number of ways=$3^6-[\binom{3}{1}*2^6-\binom{3}{2}*1^6+\binom{3}{3}*0^6]$

=540

Case 2-J1 is assigned to E1. E1 can be assigned another job

So the remaining jobs J2-J7 has to be assigned among E1-E4

number of ways=$4^6-[\binom{4}{1}*3^6-\binom{4}{2}*2^6+\binom{4}{3}*1^6-\binom{4}{4}*0^6]$

=1560

Total number of ways=540+1560

Comments

One thing i don’t get is that Why don’t you take no of ways to choose the best employee?

Why you are considering only E1 as the best employee? There should be 4 ways of doing this.