In how many ways can $4$ objects be given to $3$ persons, if each person is eligible for all the $4$ objects?

Question

In how many ways can $4$ objects be given to $3$ persons, if each person is eligible for all the $4$ objects?

Here is my approach:

1st person can take $4$ objects in $4$ ways and 2nd person can take $4$ objects in $4$ ways and 3rd person can take $4$ objects in $4$ ways, so it will be $4 \times 4 \times 4 = 64$ ways.

But my textbook has exactly the opposite approach,

Each person is eligible to get all $4$ objects, therefore each object can be given in $3$ different ways. Therefore it's $3\times 3\times 3\times 3 = 81$

I don't understand the difference between this method and my method (they both "look and sound" same to me) and yet answers they yield are different!

Can anyone explain me what cases I might be missing and why isn't textbook's and my method same?

Answer 1

Your approach, in fact, doesn't really work out because assume the objects are A, B, C, D and the persons are 1, 2, 3.

If the 1st person takes any of the four objects, say, object B, and the 2nd person takes any of the four objects, say, object B, object B will be taken twice! your answer of 64 counts many of these kinds of solutions, and also misses the fact that each person can take more than one object! More explanation: Okay, let's say that we have a certain final arrangement: maybe objects A and B go to person 1, object C goes to person 2, and object D goes to person 3. Your method doesn't account for this. It only assumes that each person can only get one object.

The second solution is in fact correct because it accounts for the possibility that more than one object goes to each person. More explanation: let's go back to our previous arrangement as (AB)(C)(D) as the final arrangement. Let's loop through each element and see "where we can put it." Let's say you're on object A right now. There are 3 people who are still "open" to taking more objects (in fact, there will always be 3 people open to take more objects, because each person can take as many as he/she wants). Thus, there are 3 ways to choose a person to own object A. Similarly, 3 ways for object B, and so on. Thus, there are 3x3x3x3 = 81 ways to do this.

Note: This cannot be reversed. You cannot say: "Oh there are 3 people; for each person we choose an object for him/her to own. There are 4 ways for the first one, 4 ways for the second, and 4 for the third for a total of 4x4x4=64 ways. This DOES NOT work. Because, there ARE NOT 4 ways for the first one. he doesn't have to take only one object.

Also, there will never be overcounting because once the objects are placed there will never be another way to place them so that the exact same arrangement is possible.

Does this answer your question? Anything else I should clarify?

Answer 2

There are actually $2^4=16$ different sets of objects that the first person can take because he can take each on or not. If the first person takes at least one, there are fewer choices for the second. What you have computed is the number of possibilities if each person takes one object with replacement. If you have a pile with lots of red, yellow, green, and blue balls and each person it to take one you get $64$ possibilities as you say.

Answer 3

Unfortunately, neither you nor the textbook is correct.

Let Persons $1,2,3$ manage Objects $A,B,C,D$

I'll list the four objects given to Persons 1 2 and 3 respectively like $ABC$ (representing $1$ gets $A$, $2$ gets $B$, and $3$ gets $C$)

Assume $1$ is given $A$. The possible choices are: $$ABC$$ $$ABD$$ $$ACD$$ $$ACB$$ $$ADB$$ $$ADC$$ That's six possible options. Multiply this result by four for when $1$ gets $B, C$ and $D$ respectively and you get $24$ ways to arrange the data.

That's one way to go about it. You can also say that $n$ objects can be arranged in $n!$ ways. Here, in terms of solving this, we can say the unallocated object goes to a Person $4$ and for this reason, there are $4!=24$ ways to arrange this.

[$n!=1\times 2\times3\times...\times n]$

Answer 4

It helps to look at extreme cases. Consider the following modification of your question:

In how many ways can one object be given to three persons if each person is eligible to receive the object?

We wish to match the object with a person. There are three ways to do this, depending on which person receives the object. Notice that we choose which person receives the object, which we can do in $3^1 = 3$ ways. The formula you attempted to use produces the incorrect answer $1^3 = 1$.

Why is your argument faulty?

You say that each person can take four objects. However, this is only possible if the same object can be given to more than one person.

In how many ways can $4$ distinct objects be given to $3$ persons, if each person is eligible to receive all $4$ objects?

You will notice that I added the work distinct to the question. If the objects were indistinguishable, only the number of objects each person receives would matter, not which objects each person receives.

We match objects with people. The first object can be given to one of the three people, as can the second, third, and fourth objects. Hence, each of the four objects can be distributed in three ways, so there are $3^4$ ways to distribute four distinct objects to three people.

Check: We consider cases.

All four objects are given to one person: There are three ways to decide which person receives all the objects.

Three objects are given to one person and the other object is given to a different person: There are three ways to select which person receives three of the objects and $\binom{4}{3}$ ways to give that person three of the four objects. That leaves two people who could receive the other object. Hence, there are $$\binom{3}{1}\binom{4}{3}\binom{2}{1}$$ such distributions.

Two objects are given to each of two people: There are $\binom{3}{2}$ ways to select two of the three people to receive two objects and $\binom{4}{2}$ ways to decide which two of the four objects will be given to the younger of those people, which also determines which objects are received by the older of the selected recipients. Hence, there are $$\binom{3}{2}\binom{4}{2}$$ such distributions.

Two objects are given to one person and each of the other people receives one object: There are three ways to select the person who receives two objects and $\binom{4}{2}$ ways to select which two of the four objects that person receives. There are two ways to select which of the remaining objects is given to the younger of the remaining people, which also determines the object that the older of the remaining people will receive. Hence, there are $$\binom{3}{1}\binom{4}{2}\binom{2}{1}$$ such distributions.

Hence, four distinct objects can be distributed to three people in $$\binom{3}{1} + \binom{3}{1}\binom{4}{3}\binom{2}{1} + \binom{3}{2}\binom{4}{2} + \binom{3}{1}\binom{4}{2}\binom{2}{1} = 3 + 24 + 18 + 36 = 81 = 3^4$$ ways.