0
$\begingroup$

Problem:

Find the number of distinct ways to distribute $5$ apples into $3$ baskets.

Visual:

Key:
a = Apple
| = Edge of a basket

So this: $$ aa|aa|a $$

Would represent $3$ baskets, the first and second baskets have $2$ apples, and the basket at the end has $1$ apple.

Number of a's = $5$
Number of |'s = $2$

Therefore: $$Let\ A := \{a,a,a,a,a,|,|\} $$ $|A|= 5+2=7$

Approach 1:

Procedure:

Using Permutations without repetition:

Note:
---"--- means "same as above"

  1. Choose an element from $A$ ($7$ choices)
  2. Choose an element from $A$ different to the previous choice ($6$ choices)
  3. ---"--- (5 choices)
  4. ---"--- (4 choices)
  5. ---"--- (3 choices)
  6. ---"--- (2 choices)
  7. ---"--- (1 choices)

So, we have: $$ 5 \times 4 \times 3 \times 2 \times 1 = 120 $$ different ways to distribute $5$ apples into $3$ baskets.

Approach 2:

$120$ seems like it's too much, so the alternative is using the Combination Formula

Combination Formula:

$$ C(n,r) = \frac{n!}{r!(n-r)!} $$

Procedure:
$$ C(7,5) = \frac{7!}{5!(7-5)!} = 21 $$ different ways to distribute $5$ apples into $3$ baskets.

The problem with this is that it counts the number of combinations of length $5$, So $2$ elements of set $A$ will have been left out.

What is the correct method to solve this problem?

$\endgroup$
1
$\begingroup$

Let $x_k$, $1 \leq k \leq 3$, be the number of apples placed in the $k$th basket. Then $$x_1 + x_2 + x_3 = 5$$ This is an equation in the nonnegative integers. A particular solution corresponds to the placement of two addition signs in a row of five ones. For instance, $$1 1 1 + + 1 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 0$, and $x_3 = 2$, while $$1 1 1 1 1 + +$$ corresponds to the solution $x_1 = 5$, $x_2 = 0$, and $x_3 = 0$. Thus, the number of ways of placing five apples in three baskets is equal to the number of ways of inserting two addition signs in a row of five ones, which is $$\binom{5 + 2}{2} = \binom{7}{2} = 21$$ since we must choose which two of the seven symbols (five ones and two addition signs) will be addition signs.

$\endgroup$
  • $\begingroup$ What I'm trying to say, is, how does $C(7,2)$ give us the number of ways of inserting | or + (for your example). $\endgroup$ – daka Mar 5 '17 at 14:04
  • $\begingroup$ Also, why does $C(7,5)$ give the same answer as $C(7,2)$. Any help would be much appreciated. $\endgroup$ – daka Mar 5 '17 at 14:44
  • 1
    $\begingroup$ Think of it this way. There are seven positions in which to place five ones and two addition signs. Choosing where to place the addition signs (or dividers) determines a particular solution to the equation. The number of such solutions is the number of ways we can choose which two of the seven positions will be filled with addition signs, which is $\binom{7}{2}$. $\endgroup$ – N. F. Taussig Mar 5 '17 at 14:53
  • 1
    $\begingroup$ As for your second question, notice that $$\binom{7}{2} = \frac{7!}{2!5!} = \frac{7!}{5!2!} = \binom{7}{5}$$ More generally, $$\binom{n}{n - k} = \frac{n!}{k![n - (n - k)!]} = \frac{n!}{(n - k)!k!} = \frac{n!}{k!(n - k)!} = \binom{n}{n - k}$$ From a combinatorial point of view, the statement that $$\binom{n}{k} = \binom{n}{n - k}$$ means the number of ways we can select $k$ of $n$ objects is equal to the number of ways we can choose not to select $n - k$ of the objects. $\endgroup$ – N. F. Taussig Mar 5 '17 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.