Distributing different jobs on different employees

Question

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.

Answer 1

You have made two fundamental errors

• You have fractionated the remaining distribution, first giving one job each to $3$ employees, then distributing the rest.
• You have used stars and bars for the distribution. Stars and bars doesn't give an equiprobable distribution, and in problems of distinct objects to distinct bins, it is normally taken that the objects are distributed uniformly at random

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.

Answer 2

You overcounted.
That is, suppose Person-1 is to get Job-1 and Job-2. You count this situation twice. Once, when the first job that goes to Person-1 is Job-1, and the second job that goes to Person-1 is Job-2. You then count this same situation, a second time. That is, you also count it when the first job that goes to Person-1 is Job-2, and the second job that goes to Person-1 is Job-1.

So, the order that (for example) Person-1 receives jobs is irrelevant, but you incorrectly distinguished between the two situations in the previous paragraph, when you should not have.

---

I agree with what true blue anil said about Stars and Bars. That is, it is not really useful when the jobs going to each person are distinct.

So, for this problem, I advise using Inclusion-Exclusion. See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

Assume that:

• The people are indexed Person-1, Person-2, Person-3, Person-4.

• The jobs are indexed Job-1, Job-2, ..., Job-7.

• Person-4 is the best employee, Job-1 is the hardest job, and Job-1 is assigned to Person-4.

• Each of the other 6 jobs are each then assigned to any one of the four people.

• It is required that Person-1, Person-2, and Person-3 are each assigned at least one job.

Using the syntax in the 2nd Inclusion-Exclusion link, let $~S~$ denote the collection of all ways that the $~7~$ jobs can be assigned, so that all of the constraints above are satisfied, except (perhaps) the constraint in the last bullet point above.

This implies that a random element in the set $~S~$ will represent some distribution of the $~7~$ jobs to the $~4~$ people, where Person-4 was assigned Job-1, and where each of the other $~3~$ people may or may not have also been assigned at least one job.

For $~k \in \{1,2,3\},~$ let $~S_k~$ denote the subset of $~S,~$ where the requirement that Person-k be assigned at least one job is violated. For example, an element in $~S_1~$ would represent a distribution of the $~7~$ jobs to the $~4~$ people, where Person-4 was assigned Job-1, Person-1 was not assigned any job, and where Person-2 and Person-3 might or might not each have been assigned a job.

Then, the desired enumeration is

$$|S| - |~S_1 \cup S_2 \cup S_3 ~|. \tag1 $$

---

Let $~T_0~$ denote $~|S| \implies $

$$T_0 = 4^6.$$

That is, for each of the $~6~$ jobs, besides Job-1, there are $~4~$ choices for who the job went to.

Let $~T_1~$ denote $~| ~S_1 ~| + | ~S_2 ~| + | ~S_3 ~|.~$
By considerations of symmetry, you have that

$$| ~S_1 ~| = | ~S_2 ~| = | ~S_3 ~| = 3^6.$$

That is, when enumerating $ ~| ~S_1 ~|, ~$ for each of the $~6~$ jobs, besides Job-1, there are $~3~$ choices for who the job went to.

Therefore,

$$T_1 = 3 \times 3^6.$$

Similarly, let $~T_2~$ denote $~| ~S_1 \cap S_2 ~| + | ~S_2 \cap S_3 ~| + | ~S_3 \cap S_1 ~|.~$
By considerations of symmetry, you have that

$$| ~S_1 \cap S_2 ~| = | ~S_2 \cap S_3 ~| = | ~S_3 \cap S_1 ~| = 2^6.$$

That is, when enumerating $ ~| ~S_1 \cap S_2 ~|, ~$ for each of the $~6~$ jobs, besides Job-1, there are $~2~$ choices for who the job went to.

Therefore,

$$T_2 = 3 \times 2^6.$$

Let $T_3 = | ~S_1 \cap S_2 \cap S_3 ~| \implies $

$$T_3 = 1^6.$$

That is, when enumerating $ ~| ~S_1 \cap S_2 \cap S_3 ~|, ~$ for each of the $~6~$ jobs, besides Job-1, there is $~1~$ choice for who the job went to.

Then, in accordance with Inclusion-Exclusion theory, the expression in (1) above is equivalent to

$$\sum_{r=0}^3 (-1)^r T_r$$

$$= ( ~T_0 + T_2 ~) - ( ~T_1 + T_3 ~)$$

$$= [ ~4^6 + ( ~3 \times 2^6) ~] - [ ~( ~3 \times 3^6 ~) + 1 ~]$$

$$= [ ~4096 + 192 ~] - [ ~2187 + 1 ~]$$

$$= [ ~4288 ~] - [ ~2188 ~]$$

$$= 2100.$$