2,179 views
0 votes
0 votes
A company hires 11 new employees, each of whom is to be assigned to one of 4 subdivisions. Each subdivision will get at least one new employee.

In how many ways can these assignments be made?

3 Answers

Best answer
4 votes
4 votes

$11$ new employees $\to$ $11$ distinct balls

$4$ subdivisions $\to$ $4$ distinct bins

Now, our problem becomes in how many ways we can distribute $11$ distinct balls to $4$ distinct bins such that no bin is empty. Solution is given by $S(11,4) \times 4!$


$\begin{array}{ccccccccccc}1\\1 &1\\1 & 3& 1\\1 &7&6 & 1\\
1 &15&25 & 10 & 1\\
1 &31&90 & 65 & 15&1\\
\vdots
\end{array}$

We get $S(11,4)$ on the $11^{th}$ row and $4^{th}$ column. 


Alternatively, we can solve the problem using Inclusion-Exclusion principle. 

Total no. of ways to put $11$ distinct balls to $4$ distinct bins (bins can be empty) $ = 4^{11}$ as for each of the $11$ balls we have $4$ choices. Now, we subtract the cases where $11$ balls can go to $3$ bins (again allowing empty bins). But in this subtraction we over count the cases where balls go to just $2$ bins. So, now we have to add those cases and continue this addition and subtraction till we get a single bin. i.e., our required answer will be 

$4^{11} - {}^4C_3 \times 3^{11} + {}^4C_2 \times 2^{11} - {}^4C_1 \times 1$

edited by
2 votes
2 votes

There is a standard template for solving such questions.(Star and Bar Method). This problem can be reduced to that.

0 votes
0 votes

Here As mention "at least 1"

Given data : 11 new Employees, 4 subdivision. Condition: at least one employee should go each subdivisions.

 

Required No. of ways= Total ways without restriction - total ways which violates the restriction

Total ways without restriction:

(use 11 employees as set 1 and 4 subdivisions as set 2)

i.e. total possible mapping= 411

Total ways which violates the restriction:

=all employees mapped to any of 3 subdivisions+ all employees mapped to any of 2 subdivisions + all employees mapped to any of 1 subdivisions

= 311 * C(4,3) - 211 * C(4,2) + 111 * C(4,1)   (here i have to use - for explanation watch the video link given in comment of Arjun's sir Answer.)

= 7,20,880

Required No. of Ways= 411 - 311 * C(4,3) + 211 * C(4,2) - 111 * C(4,1) 

  = 34,98,000

 

edited by