Kenneth Rosen Edition 6th Exercise 6.6 Question 11 (Page No. 457)

Question

In how many different ways can seven different jobs be assigned to four different employees so that each employee is assigned at least one job and the most difficult job is assigned to the best employee?

I got the first point that we need to find out the number of onto functions for a set with 7 elements to a set with 4 elements. But how to deal with the second part that most difficult job is assigned to the best employee?

Answer 1

Most difficult job and best employee both are unique so this assignment can be done only in 1 way.
Now we have to divide remaining 6 jobs into 4 employees

$\color{RED}{Approach \ 1} -$
Possible assignments are-

$1. \{4,1,1,0\}$
$2. \{3,2,1,0\}$
$3. \{2,2,2,0\}$
$4. \{3,1,1,1\}$
$5. \{2,2,1,1\}$
$\color {Blue}{Note-}$ In $1^{st} \ \ 3 \ cases $ , exactly $1$ job is assigned to best employee.

$Case \ 1 \rightarrow \large \binom{6}{4}.\binom{2}{1}.\binom{1}{1}.\frac{3!}{2!} = 90$

$Case \ 2 \rightarrow  \large \binom{6}{3}.\binom{3}{2}.\binom{1}{1}.{3!} = 360$

$Case \ 3 \rightarrow \large  \binom{6}{2}.\binom{4}{2}.\binom{2}{2}.\frac{3!}{3!} = 90$

$Case \ 4 \rightarrow \large  \binom{6}{3}.\binom{3}{1}.\binom{2}{1}.\binom{1}{1}.\frac{4!}{3!} = 480$

$Case \ 5 \rightarrow \large  \binom{6}{2}.\binom{4}{2}.\binom{2}{1}.\binom{1}{1}.\frac{4!}{2!.2!} = 1080$

Possible Number of ways = $90+360+90+480+1080 = \color{Green}{2100}$

$\color{RED}{Approach \ 2} -$
https://gateoverflow.in/79804/permutation-combo

Comments

@Srestha,

Seven same jobs be assigned to four different employees.

Use Star and bar method.
Answer will be $\binom{7+4-1}{4-1} =\binom{10}{3} = \binom{10}{7}$ 

---

I will add some more information which can help in understanding approach 1.

So we have 7 different jobs to be given to 4 employees.

Now the toughest job will be only 1 and best employee will be only one so there is only one way to give toughest job to the best employee.Now, there are 2 cases

Case 1: The best employee is happy with toughest job and wants no more job- In this case now we have to distribute 6 jobs to 3 people such that each get atleast 1.

This we will do by 2 step method

(a)Form all possible non-empty 3 groups out of total available 6 jobs.

(b)Distribute 3 groups to 3 employees

Let three groups be G1 G2 G3.

I will start numbering the number  of jobs in each group in a non-decreasing order, first by assigning the highest number possible to G1, and then to G2, and so on..

First partition $P_1$ is 

G1	G2	G3
4	1	1

After we have given 4 jobs to G1, we can only assign 1 Job to G2 else G3 will be empty because total jobs are 6 only.

Now number of ways in which we can distribute 6 jobs into 3 non-empty groups  of above size will be

$\frac{6!}{4!.(1!)^2.2!}$

Let this be $n(P_1)$

Now Consider these 3 groups are 3 different objects and we can distribute them to 3 different employees in 3! ways.

So, number of ways in which I can assign 6 jobs to 3 employees  such that one gets 4 job, and rest two get 1 job each is $n(P_1)*3!$ ways and this comes out to be 90.

Now , second possible group denoted by $P_2$ can be (Remember, now to maintain non-decreasing order, I will subract one quantity from G1, and will give to G2.)

$P_2$ 

G1	G2	G3
3	2	1

Number of ways of grouping 6 jobs into above groups = $\frac{6!}{3!.2!}$ say this is $n(P_2)$

Now distributing this group specification to 3 employees in 3! ways, so total ways =

$n(P_2)*3!$ and this comes to be 360.

Now we will try to form another grouping by subtracting 1 from G1 in P2 and give it to G3 (Remember non-decreasing order has to be maintained). I cannot subtract 1 from G2 in P2 above and give it to G3 because then grouping will be 3,1,2 which will be not non-decreasing.

So next possible grouping is say $P_3$

G1	G2	G3
2	2	2

Number of ways of this grouping from 6 jobs = $n(P_3)=\frac{6!}{(2!)^3.3!}$

And now I can assign these groups to 3 employees in $n(P_3)*3!$ ways=90.

Now you will question me that how can you distribute 3 groups of sizes 2,2,2 to 3 employees in 3! ways. Well, definitely these groups are same in size, but the content in it (means the jobs) are not unique every time say G1 first may contain job J1J2 and then it may contain job J3J4.

So, if an employee e1 receives G1 the first time and G2 the second time, the jobs may not be of equal type in G1 and G2.

Now total ways for Case 1

$(n(P_1)*3!)+(n(P_2)*3!)+(n(P_3)*3!) = 540$

Case 2: The employee given Toughest job is not happy and wants more job. In this case remaining 6 jobs need to be distributed to 4 employees. Procedure remains the same. First do grouping and then distribute.

Next partition we form is $P_4$ using the same non-decreasing method.

G1	G2	G3	G4
3	1	1	1

Number of ways of this grouping $n(P_4)=\frac{6!}{3!.(1!)^3.3!}$

These 4 groups can be distributed to 4 employees in 4! way. So total, $n(P_4)*4!$

Next partition $P_5$

G1	G2	G3	G4
2	2	1	1

Number of ways of grouping $n(P_5)=\frac{6!}{2!.2!.1!.1!.2!.2!}$

Number of ways in which 6 jobs can be assigned to 4 employees is $n(P_5)*4!$

Now, no more partitions of 6 jobs into 4 non-empty groups can be made.

So total ways for Case 2 = $n(P_4)*4!+n(P_5)*4! \,=1560$

So, total number of ways is 540+1560=2100.

---

Say, E1 is given {J1,J3,J5,J6} 
E2 is given {J4} 
E3 is given {J2} 

OR

Say, E2 is given {J1,J3,J5,J6} 
E1 is given {J4} 
E3 is given {J2}

@Soumya

are these not two different condition?

then why dividing by 2!? 

Answer 2

I think best employee is only 1 and difficult job is only one so left over is 6 and 3 , now do again as you did for previous problem

Comments

You mean to say I have to find now number of onto functions from a 6 element set to a 3 element set?

---

It ain't working that way.!!

---

Yes because how you can select difficult job and best employee . now say we have 3 employee  and 6 job .assign 1 job each it makes 6-3 =3 job left over. those three job can be assign in3!*6C3 as we have to select 3 jobs .now, 6P3 *( 3 job to 3 employee) it can be done in (4^3) as so answer would be ((6P3)*4^3) why 4 because 3 for job and 1 not assigning any job. If iam somewhere wrong  rectify me.

Answer 3

in this question employees have to numbered and  jobs need to numbered

you have assign most difficult problem to best employee always..... remove that job...


 with remaining 6 jobs ... assign 3 jobs to remaining 3 employees why because every employee has to do atleast one job...  C(6,3) * 3! 

therefore you have 3 more jobs but this time you can assign this jobs to anybody.

 

1) assign all 3 jobs to one employee ----> e1,e2,e3,e4  ====> 4 possibilities

 

2) assign 2 jobs to one employee and 1 job to another employee ----> choosing 2 employees from 4 ---> 6*2 ( permute the employees accroding to no.of jobs ) ==> 12 * 3 ( permute the jobs ) = 36


3) assign 1 job to one employee ----> choosing 3 employees from 4 ===> 4*3! ( permute the jobs ) = 24

total possibilities = ( C(6,3)* 3! ) (4+36+24) = 120 * 64 = 7680

Comments

The problem here is you are overcounting the jobs distributed ti employees

When you choose 3 jobs out of 6 and distribute to 3 employees and after that you distribute remaining jobs to remaining employees,

Say you have an employee e1, who got job J1 from 6C3 and J2 after that,and in some other case he may get Job J2 from 6C3 and Job J1 after that and these both are counted twice in your counting but these are actually one case only.

You actually need to do the grouping of jobs and then distribute them to employees.

---

Question on Similar concept and I did same mistake there.
https://gateoverflow.in/46964/cmi2014-a-01
Check comments just below the question. 

---

Thank u @Ayush Upadhyaya  and @Soumya29

for analyzing and identifying where the fault is.

Answer 4

Lets solve it without formula

Three condition is there

$1)$ Distinguishable job distinguishable employee

$2)$ Each employee got atleast 1 job

$3)$ Most difficult job to best employee

Say there are $J_{1},J_{2},J_{3}, J_{4},J_{5},J_{6},J_{7}$ and $4$ employees are $E_{1},E_{2},E_{3}, E_{4}$

Now say $J_{7}$ is most difficult job and $E_{4}$ is best employee

So, $J_{7}$ is fixed for $E_{4}$

Now, rest $6$ jobs we can divide in $4$ employees, So, that each employee can get $1$ job atleast

--------------------------------------------------------------------------------------------------------------------------------------------

First think about the combination $\left \{ 3,1,1,1 \right \}$

here 1,2,3.....,6 represents  $J_{1},J_{2},J_{3}, J_{4},J_{5},J_{6}$ and only first $3$ ways of choosing we have shown ,because rest two we can choose only 1-1 ways


$\left \{ 1,5,6 \right \}$

$\left \{ 1,4,6 \right \}$

$\left \{ 1,3,6 \right \}$

$\left \{ 1,2,6 \right \}$

$\left \{ 1,4,5 \right \}$

$\left \{ 1,3,5 \right \}$

$\left \{ 1,2,5 \right \}$

$\left \{ 1,3,4 \right \}$

$\left \{ 1,2,4 \right \}$

$\left \{ 1,3,2 \right \}$

-------------------------------------

$\left \{ 2,3,4 \right \}$

$\left \{ 2,3,5 \right \}$

$\left \{ 2,3,6 \right \}$

$\left \{ 2,4,5 \right \}$

$\left \{ 2,4,6 \right \}$

$\left \{ 2,5,6 \right \}$

-------------------------------------------

$\left \{ 3,4,5 \right \}$

$\left \{ 3,4,6 \right \}$

$\left \{ 3,5,6 \right \}$

$\left \{ 4,5,6 \right \}$

So, number of possible ways in $\left \{ 3,1,1,1 \right \}$ combination will be 20

===================================================================

Now another combination possible here i.e. $\left \{ 2,2,1,1 \right \}$
 

here 1,2,3.....,6 represents  $J_{1},J_{2},J_{3}, J_{4},J_{5},J_{6}$ and only first $2$ ways of choosing we have shown 

Combinations are


$\left \{ 1,2 \right \}$

$\left \{ 1,3 \right \}$

$\left \{ 1,4 \right \}$

$\left \{ 1,5 \right \}$

$\left \{ 1,6 \right \}$

$\left \{ 2,3 \right \}$

$\left \{ 2,4 \right \}$

$\left \{ 2,5 \right \}$

$\left \{ 2,6 \right \}$

$\left \{ 3,4 \right \}$

$\left \{ 3,5 \right \}$

$\left \{ 3,6 \right \}$

$\left \{ 4,5 \right \}$

$\left \{ 4,6 \right \}$

$\left \{ 5,6 \right \}$

-------------------------------------------------

Now for each first 2 combination, there is again $6$ combinations

here 1,2,3.....,6 represents  $J_{1},J_{2},J_{3}, J_{4},J_{5},J_{6}$ and only second $2$ ways of choosing we have shown 

Say, for $\left \{ 1,2 \right \}$ the $6$ combinations are

$\left \{ 3,4 \right \}$

$\left \{ 3,5 \right \}$

$\left \{ 3,6 \right \}$

$\left \{ 4,5 \right \}$

$\left \{ 4,6 \right \}$

$\left \{ 5,6 \right \}$

So, total number of ways will be $15\times 6=90$ i.e. 90

So, total number of ways 20+90=110

======================================================================

======================================================================

If the same question I do by indistinguishable office and distinguishable employee, it will be answer as

$\binom{6+4-1}{4-1}=84$ ways

Is there anything I missing?