How many ways we can distribute 10 distinct objects among 4 persons such that each person gets at most 9 objects?

Given the question:

"How many ways we can distribute $$10$$ distinct objects among $$4$$ persons such that each person gets at most $$9$$ objects?"

The correct answer given is $$4^{10} -4$$. We have subtracted the 4 cases in which each person gets all 10 objects.

Can't the answer be $$10 \cdot 4^9$$? We have $${10 \choose 1}$$ ways of selecting an object. We remove that object and now each object has $$9$$ choices. So each object can now get at most $$9$$ objects only.

• This is hard to follow. You appear to be using "object" to refer to both the objects and the people receiving the objects. In any case, I can't understand the computation you propose.
– lulu
Commented Oct 27, 2022 at 11:32
• You are leaving out one object and only distributing the other 9. That removed object is also supposed to be given to someone. Commented Oct 27, 2022 at 11:40
• @JaapScherphuis Am I not covering that when I am taking the other 9 cases when I am including that object? Commented Oct 27, 2022 at 12:18
• When are you counting the cases where two people each get 5 objects and two people each get none? Commented Oct 27, 2022 at 12:29
• In fact all the cases you do count are different from what the question asked for. For example, one of the cases you count is the first person gets nine objects and the other three get none. But you were supposed to distribute ten objects. So you still have to give the last object to somebody, which you haven't done. Commented Oct 27, 2022 at 13:17

First, I propose a different derivation of the answer $$4^{10}-4$$ that goes into the direction of your way of thinking.

Let us say that we distribute the first 9 objects.

• There are $$4^9$$ ways to do so. In all those cases except 4, i.e. $$4^9-4$$, each person received at most 8 objects, so we can safely distribute the last one as we prefer, so in 4 different ways.

• We get a total of $$(4^9-4)\cdot4$$ total ways of distributing the objects.

• We are left with the 4 cases in which someone already received 9 objects.

• In these 4 cases, we can distribute the remaining object to a different person, so in 3 different ways.

The total is thus: $$(4^9-4)\cdot 4 + 4\cdot 3 ,$$ which is equal to $$4^{10}-4$$.

Then, your proposal is to start by removing one of the 10 objects, not necessarily the last one, say the $$n$$th. You have 10 different ways of doing so.

Then, for each $$n$$, we follow the reasoning above and we get $$4^{10}-4$$ different ways. But you get all the different ways of distributing for each $$n$$, so you do not have to multiply times 10.

• I didn't completely get your 2nd point but I try to work on it. Commented Oct 27, 2022 at 15:35
• Second bullet point: in 4^9-4 different arrangements of the first 9 objects, you can arrange the last in 4 different ways, for a total of (4^9-4)*4 ways. Commented Oct 27, 2022 at 15:40