edited by
2,590 views
0 votes
0 votes
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?
edited by

4 Answers

Best answer
4 votes
4 votes

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

selected by
0 votes
0 votes
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
0 votes
0 votes

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

edited by
0 votes
0 votes

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?

edited by

Related questions

0 votes
0 votes
0 answers
1
1 votes
1 votes
2 answers
2
0 votes
0 votes
1 answer
3
Dexter asked Oct 21, 2016
2,677 views
How many derangements of (1 2 3 4 5 6 ) end with integer 1 2 and 3 in some order ?