Discrete math - confusion in onto functions

174 Views Asked by At

The question that I'm trying to solve is:

At the CH Company, Joan, has a secretary Teresa, and three other administrative assistants. If seven accounts must be processed, in how many ways can Joan assign the accounts so that each assistant works on at least one account and Teresa's work includes the most expensive account?

(Grimaldi p.288)

I approached this question as distributing identical objects into distinct containers where no container left empty and the repetitions were allowed. So,

x1+x2+x3+x4=3 (I distributed 4 of them to the containers and left with 3 more accounts)

So the rest (at least for me) was C(6,3). But apparently It was wrong. Where did I make the mistake? Because in solution it just goes through it without any trace of explanation.

Solution in the book is, with my words:

Since this is an onto function where the domain is the accounts and the codomain is the employees, then applies the number of onto functions formula to case by case.

As mentioned above it divides into two cases in which the first case; Teresa (secretary) works only on the most expensive account. And the second case; Teresa works on the most expensive one along with other accounts.

The answer is 540+1560=2100.

2

There are 2 best solutions below

2
On BEST ANSWER

I think you have to assume you are distributing distinguishable objects into distinct containers. You need to use Stirling numbers of the second kind or something similar.

The answer in the book seems to be $S_2(6,3)\times 3! + S_2(6,4)\times 4! = 90 \times 6 + 65 \times 24$.

I might do it another way and say that you have to distribute $7$ accounts onto $4$ people, though only a quarter of these give Teresa the most expensive account, so $\frac14 \times S_2(7,4) \times 4! = \frac14 \times 350 \times 24$, which gives the same answer.

0
On

Observe that both the accounts and the people to whom they are assigned are distinguishable.

Case 1: Teresa works only on the most expensive account.

Joan must distribute six accounts to the other three administrative assistants. If there were no restrictions, Joan could assign each of the six accounts to one of three people. There are $3^6$ ways to do this since there are three choices for each of the six accounts. However, we must exclude those assignments in which an administrative assistant is not assigned at least one account. There are $\binom{3}{1}$ ways of selecting one assistant to not receive any accounts and $2^6$ ways of assigning the six accounts to the other two assistants. There are $\binom{3}{2}$ ways of selecting two assistants to not receive any accounts and $1^6$ ways of assigning the six accounts to the remaining assistant. By the Inclusion-Exclusion Principle, there are $$3^6 - \binom{3}{1}2^6 + \binom{3}{2}1^6$$ ways to assign the other six accounts if Teresa only works on the most expensive account.

Case 2: Teresa works on at least one other account in addition to the most expensive one.

If there were no restrictions, Joan could assign each of the six other accounts to one of four people. Since there are four choices for each of the six accounts, she could do this in $4^6$ ways. From these assignments, we must exclude those in which one of the administrative assistants is not assigned at least one account. By a similar argument to that given above, the number of ways the six remaining accounts can be assigned to the four assistants so that each person receives at least one is $$4^6 - \binom{4}{1}3^6 + \binom{4}{2}2^6 - \binom{4}{3}1^6$$

Since these cases are mutually exclusive, the number of possible ways Joan can assign the accounts so that Teresa handles the most expensive account and each administrative assistant handles at least one account is

$$3^6 - \binom{3}{1}2^6 + \binom{3}{2}1^6 + 4^6 - \binom{4}{1}3^6 + \binom{4}{2}2^6 - \binom{4}{3}1^6$$