What is the total number of ways to distribute $20$ oranges to $3$ students such that each gets at least $1$ orange?

Question

Here's the question:

What is the total number of ways to distribute $20$ oranges to $3$ students such that each gets at least $1$ orange?

(I come to fact that each orange is distinct or not at the end.)

Sounds very simple. The way I approach this is to first give each of the $3$ children an orange each and then distribute the rest.

Let $A$, $B$ and $C$ be the $3$ children.

STEP 1. The number of ways to give them an orange each to start with is $C(20, 3) \cdot 3!$ This is to say there are $C(20, 3)$ ways to pick the initial set of oranges and $3!$ ways to rearrange them. This could also be written as $P(20, 3)$ if I am not wrong.

STEP 2. Now to distribute the remaining oranges, let's take the stack of the remaining $17$ oranges.

1st orange from the stack has $3$ children to pick from so the # of ways to choose is $3$.

2nd orange from the stack has $3$ children to pick from so the # of ways to choose is $3$.

.

.

.

So the total ways to distribute the remaining stack is $3•3•3... 17$ times $= 3^{17}$.

Hence the total number of ways to distribute 20 oranges to 3 children, with each getting at least 1 orange is:

$P(20, 3) \cdot 3^{17}$

well, maybe (I know it's wrong but at least seems plausible)

I figured something was wrong with this approach when I thought okay... what if the oranges are all the same?

Well, then the order wouldn't matter. And since there are 20! ways to arrange 20 oranges, for identical oranges, you just divide the answer of distinct oranges by 20!

So for the case of identical oranges, the Total # of ways = $P(20, 3) \cdot 3^{17} / 20!$

But $P(20, 3) = 20!/17!$.

The the Total # of ways = $(20!/20!) \cdot (3^{17}/17!) = 3^{17}/17!$, And ofc, 17! consists of terms that are not multiples of 3. So that's a fraction! But the total number of ways can't be a fraction.

WHAT DID I DO WRONG?

Answer 1

The Mistake

At the beginning, you give each person one orange. In doing so, you create a distinction that shouldn't exist: for each person there is the first orange and there are the rest, and this cause double counting. For example, consider a distribution where the first person gets oranges $A$, $B$, and $C$. You calculate this exact distribution three times:

1. First person initially gets orange $A$, then gets oranges $B$ and $C$
2. First person initially gets orange $B$, then gets oranges $A$ and $C$
3. First person initially gets orange $C$, then gets oranges $A$ and $B$

Indistinguishable Oranges

For identical or indistinguishable oranges, simply use stars and bars:

$$ \binom{20-1}{3-1}=\binom{19}{2} $$

Distinct Oranges

For distinct oranges, simply use Principle of Inclusion and Exclusion (PIE):

$$ 3^{20}-3\cdot 2^{20} + 3\cdot 1^{20} $$

Answer 2

Thank you, everyone, for helping me out on this.

STARS AND BARS METHOD

Let us first consider the case of identical oranges.

The first thing you do is give an orange to each of the students. Since the oranges are identical, there is only 1 way to do it, no combinatorics are required as such.

then, you take a chain of 17 remaining oranges and partition them into 3 parts, i.e. add 2 divisions within the chain.

1_2_3_4_5_6_7_8_9_10_11_12_13_14_15_16_17

here, '_' represents a space for the partition.

Note how there is a space at the ends of the chain too since we can allow a student to get 0 oranges since we already distributed 1 to each

there are C(19, 2) ways to pick the spots for partition; hence C(19, 2) to distribute oranges in the required way.

[This could also be simply understood by the following: 1_2_3_4_5_6_7_8_9_10_11_12_13_14_15_16_17_18_19_20 this time, we take all 20 oranges and use the partition method/ stars and bars method with the number of partitions within the chain since no student can get less than 1 orange. again, we see the total # of ways is C(19, 2)... this is the same as the method before in essence.]

Now to the case of distinct oranges. The answer has to be different. So directly applying the Stars and Bars method doesn't work.

Thinking it through, say we have the following case:

1_2_3_4_5_6_7_8_9|10_11_12_13_14_15|16_17_18_19_20

The bars are b/w (9,10) & (15,16)

We can see, that no matter how we arrange these bars, there is no way we can have student A have Orange#1 and Orange#20. This is, however, one of the cases we must consider since all oranges are now distinct. Applying a simple permutation to the initial arrangement wouldn't work either. because...

1_20_3_4_5_6_7_8_9|10_11_12_13_14_15|16_17_18_19_2

even if the above case is a different swap(20, 2)

9_2_3_4_5_6_7_8_1|10_11_12_13_14_15|16_17_18_19_20

this case is the same as the first one since the order of oranges given to a specific student doesn't matter.

EDIT (Courtesy, @Rezha_Adrian_Tanuharja):

My approach was wrong as it double counted too. (Quite a nasty problem this one is eh!)

I don't know how the result in one of the other answers came into being but here's how I break it down:

The Correct Approach (For distinct Oranges):

Pretend there is no restriction!

Total # Ways to distribute = 3^20

Now, Subtract the cases for which at least 1 of the students does not get an orange.

The probability that Student A doesn't receive the orange while handing out a single orange = 2/3

Hence the probability of Student A not receiving any orange at all = 2^20/3^20

Hence, the total cases where student A does NOT receive any orange is (total cases) * (probability of Student A not receiving an orange)

= 3^20 * 2^20/3^20 = 2^20

The same goes for Students B, C and D. Hence, cases where one of the students doesn't receive an orange = 3 * 2^20

Now time for the greedy case of only 1 person getting all the oranges and 2 not getting a single orange.

Again, this for the base case is 1/3 hence total probability is 1/3^20

Thus, the total ways in which only student A gets all the oranges is

3^20/3^20 = 1

Thus the total ways in which any of the 3 gets all oranges is

3 * 3^20/3^20 = 3 {Since any of students A, B or C can be the greedy/lucky one}

VERY CHEEZY BIT

You might think the answer is 3^20 - 3•2^20 - 3•1^20 but, looking at the answer we had in another one of the answers, we have 3^20 - 3•2^20 + 3•1^20

Why an addition you might wonder... because there again is a double count!

(I realized this after some time of thinking)

For the cases where Student A received no orange, we already had an instance where Student B didn't receive the oranges as well as a case where Student C didn't receive the oranges. And yes, only 1 case since there is only 1 way a single student receives all the oranges.

So by adding Cases where A, B and C did not receive any oranges, we double counted those in which only 1 student received all the oranges as well.

In short, while calculating the cases in which a student got no oranges, we included 3 * 2 = 6 cases where only 1 student got all the oranges. But there are only 3 such cases. Thus finally, we get...

The total number of ways in which we can distribute 20 distinct oranges to 3 different students is 3^20 - 3•2^20 + 3•1^20

FINAL EDIT

All right, several months later, I came back to studying permutation and combination and realised what this has to do with Inclusion & Exclusion...

The entire problem can neatly be described by a Venn Diagram with 3 circles, each representing spaces of a particular person not receiving any orange. They have no common space of intersection (since you can not distribute oranges such that no one gets any oranges).

The actual answer (Number of permutations for which each gets at least 1 orange) is Total - Union(Circles)