Think you can count? We’re in a cafeteria with a fruit basket.

An arrangement of objects into a sequence, where order matters, is a permutation. A collection of objects, when the order does not matter, is a combination.

Counting permutations

Here, we consider the choices of fruit among our three friends, Christina, Joaquin, and Ezra. Because Christina, Joaquin, and Ezra are in line at the cafeteria, the order matters.

Case 1. Christina, Joaquin, and Ezra each select one fruit. There are plenty of bananas , strawberries , watermelons , and green apples in the cafeteria. How many different outcomes are there? e.g., one outcome is Christina and Ezra select a banana and Joaquin selects a watermelon.

Each person individually has four different outcomes. Since there are three people and any one person’s choice does not change the possible outcomes of the others, the number of outcomes is $4\times4\times4=4^3$.

More generally, when $k$ people each have a choice of $n$ fruits, the number of outcomes is $n^k$. This is called a permutation with repetition since people may choose the same fruits.

Case 2. Christina, Joaquin, and Ezra each select one fruit. Now, however, there is only a single banana , green apple , and strawberry remaining in the fruit basket. How many different outcomes are there?

Now, since Christina is in line first, she has a choice between all three fruits. However, after she chooses one, there are only two choices remaining for Joaquin; Ezra gets one choice. So, here the number of different outcomes is $3\times 2 \times 1$.

More generally, given $n$ people lined up to select $n$ distinguishable fruits, the number of outcomes is: $n(n-1)(n-2)\cdots (3)(2)(1).$

This is called the factorial of $n$, denoted as $n!$.

Case 3. Christina, Joaquin, and Ezra each select one fruit. Now, however, there is a banana , green apple , strawberry , and watermelon remaining in the fruit basket. How many different outcomes are there?

There are four fruits for three people. One fruit will be left behind. Following the logic above, Christina has four choices, Joaquin has three choices, and Ezra has two choices. So there are $4\times 3 \times 2$ outcomes.

More generally, when $k$ people each choose one of $n$ distinguishable fruits, for $n\geq k$, the number of outcomes is: $n(n-1)(n-2) \cdots (n-k+1).$

There are $k$ factors here, one for each person. Note that this can be written as:

$$\frac{n!}{(n-k)!}.$$

This scenario, where we seek the number of orderings of a subset of $k$ objects from a set of $n$ distinguishable objects is called a $k$-permutation of $n$.

Case 4. Christina, Joaquin, and Ezra each selected one fruit. We know that, all together, Christina, Joaquin, and Ezra selected two bananas and a watermelon, but we don’t know who selected which fruit. How many different possibilities are there? e.g., one possibility is that Christina selected the watermelon and Joaquin and Ezra each selected a banana.

Here, we seek how many different ways we can distribute two bananas and a watermelon among Christina, Ezra, and Joaquin, under the constraint that each receives one fruit. This seems similar to Case 2, where we counted the permutations of three different, distinguishable fruits. But, in this scenario, the two bananas are indistinguishable. i.e., if we could label the bananas with 1 and 2, the assignment:

Christina: , Ezra: $_1$, Joaquin: $_2$

is the same as the assignment:

Christina: , Ezra: $_2$, Joaquin: $_1$

since both describe the scenario where Christina gets the watermelon and Joaquin and Ezra get a banana.

That is, $3!$ overcounts the number of possibilities because, upon switching the two labeled bananas in each assignment, the assignment represents the same outcome. Consequently, we must then divide the answer for the distinguishable fruit case ($3!$) by the number of ways we can permute the bananas. Since there are two bananas, we need to divide by $2!=2$. Thus, there are $3!/2! =3$ outcomes here:

1. Christina: , Ezra: , Joaquin:
2. Christina: , Ezra: , Joaquin:
3. Christina: , Ezra: , Joaquin:

From the list above, we see that we could also reduce this problem to: who gets the watermelon? Then, there are only 3 choices.

More generally, consider when we have $n$ fruits consisting of $k$ different (distinguishable) kinds fruit. Let $n_i$ be the number of fruits of type $i$ (e.g. here, $n$$=2$ and $n$$=1$); we have $k$ of these variables, and a constraint here is:

$$n_1 + n_2 + \cdots n_k = n.$$

The number of permutations is

$$\frac{n!}{n_1! n_2! \cdots n_k!}.$$

The $k$ numbers in the denominator– one for each type of fruit– are to account for the indistinguishability of these fruits, as we did for the bananas in this case. This is called a multiset permutation.

Counting combinations

Here, we will see examples where the ordering of the fruits does not matter by considering only Christina’s selection of fruit from the basket.

Case 5. Christina selects two different fruits from a fruit basket that contains a banana , a strawberry , a watermelon , and a green apple . How many different outcomes are there? e.g., one outcome is that she selects a watermelon and a strawberry. Here, the ordering of the fruit does not matter.

If ordering did matter, we would count the $k=2$ permutations of $n=4$; Christina has four choices for the first fruit and then three remaining choices for the second fruit she picks, giving $4\times 3$ outcomes. However, we need to correct for the fact that, here, since ordering does not matter,

{ , }

is the same as

We can correct for this overcounting by dividing by the number of permutations (reorderings) of the two fruits that Christina selected, which in this case is $2!=2$. There are thus $4 \times 3 / 2 = 6$ different outcomes here.

We will use the brackets {} to denote a set of objects where ordering does not matter. All outcomes here are then:

1. {, }
2. {, }
3. {, }
4. {, }
5. {, }
6. {, }

More generally, following the math for $k$-permutations of $n$ in Case 3, the number of combinations of $k$ fruits from a basket of $n$ distinguishable fruits ($k=2$, $n=4$ in this case) is:

$$\frac{n!}{(n-k)! k!}.$$

So the formula gives the number of $k$-permutations of $n$ divided by $k!$, the number of ways to permute/rearrange an ordered sequence of $k$ fruits, to correct for the order being inconsequential.

The number of combinations of $k$ objects from a set of $n$ distinguishable objects has a special notation:

$$\binom{n}{k} := \frac{n!}{(n-k)! k!},$$

read out loud as “$n$ choose $k$”.

Case 6. Christina selects two fruits from a fruit basket with four different types of fruit (bananas , strawberries , watermelons , and green apples ). However, we now relax the constraint in Case 5 by allowing duplicates; Christina can select two of the same fruit if she desires. How many outcomes are there? Again, ordering does not matter.

There is a visual way to understand this problem. To represent a particular outcome, let’s list the fruits that Christina chooses in a special way, using cookies from the cafeteria. We place $n-1=3$ cookies in a row on the table:

When Christina chooses two fruits, we group them together by fruit type (e.g. bananas with bananas) and place them in between the cookies, using the cookies as separators. Our convention is to place the fruits in the following order: bananas, strawberries, watermelons, and then green apples.

For example, if she chooses a banana and a watermelon, we represent this as:

If she chooses two watermelons:

If she chooses a watermelon and a green apple:

That is, we keep a cookie to separate the fruit type even if there were no fruits of that type. This way, no matter what the outcome, there are always $k=2$ fruits and $n-1=3$ cookies in our representation of an outcome, for a total of $k+n-1=5$ foods representing the outcome.

From this representation of outcomes, we see that the number of outcomes is equal to the number of ways that we can arrange the $n-1=3$ cookies in $k+n-1=5$ positions (the rest of the positions will be occupied by fruits). This is a multiset permutation as in Case 4, where we are looking for the number of permutations of $k+n-1$ symbols, of which $n-1$ are indistinguishable cookies and the other $k$ symbols are fruits, which we also view as indistinguishable since the positions of the cookies distinguish the fruits implicitly by our convention of ordering the fruit.

The number of ways we can arrange the $n-1$ cookies among the $k+n-1$ positions is:

$$\frac{(k+n-1)!}{k! (n-1)!} = \binom{k+n-1}{k}.$$

In this particular case, $\binom{2+4-1}{2}=10$. We now check by enumerating the possibilities. We have four more possibilities than in Case 5 above, since we now allow for duplicates:

1. {, }
2. {, }
3. {, }
4. {, }
5. {, }
6. {, }
7. {, }
8. {, }
9. {, }
10. {, }

This scenario is counting the number of $k$ combinations of $n$ objects with repetitions. This type of counting also has a special notation:

$$\left( \binom{n}{k} \right):= \frac{(k+n-1)!}{k! (n-1)!} = \binom{k+n-1}{k}$$ comments powered by Disqus