Category: Combinatorics

Milkshakes, Beads, and Pascal’s Triangle

College Mathematics, Combinatorics, High School Mathematics

Note: This is the first part of the Binomial Theorem Series

Binomial Theorem I: Milkshakes, Beads, and Pascal’s Triangle

Binomial Theorem II: The Binomial Expansion

*************************************

The Milk Shake Problem

Problem 1: Issa went to a shake kiosk and want to buy a milkshake. The shake vendor told her that she can choose plain milk, or she can choose to combine any number of flavors in any way she want. There are four flavors to choose from: Apple, Banana, Chico, and Durian.

How many possible combinations can Issa create?

It is clear that Issa can choose her milk shake to have no flavor (pure milk shake), one flavor, two flavors, three flavors, or four flavors. The possible combinations are shown below.

Table 1

» Read more

6 comments , , , , , , , , , ,

Why is 0! equals 1?

College Mathematics, Combinatorics, Questions and Quandaries

Many books will tell you that 0! equals 1 is a definition. There are actually a few reasons why this is so – the two of which are shown below.

Explanation 1:

Based on my Introduction to Combinations post, we can conclude that n taken n at a time is equal to 1. This means, that there is only one way that you can group n objects from n objects. For example, we can only form one group consisting of 4 letters from A, B, C and D using all the 4 letters.

From above, we know that the \displaystyle{n \choose n} = 1. But, \displaystyle{n \choose n} = \displaystyle\frac{n!}{(n-n)!n!} = \displaystyle\frac{n!}{0!n!} = 1. To satisfy the equation, 0! must be equal to 1.

Explanation 2:

We can also use the fact that n! = n(n-1)!. Dividing both sides by n, we have \displaystyle\frac{n!}{n} = (n-1)!. If we let n = 1, we have \displaystyle\frac{1!}{1} = (1 - 1)! \Rightarrow 1 = 0! which is what we want to show.

Explanation 3

We can also use the following pattern. We know that n! = n(n-1)(n-2)(n-3) \cdots 3(2)(1) which means that

n! = n(n-1)!.

Dividing both sides of the equation by n, we have

(n - 1)! = \frac{n!}{n}

Using this fact, we can check the following pattern.

4! = \displaystyle \frac{5!}{5} = \frac{(5)(4)(3)(2)(1)}{5} = 24

3! = \displaystyle \frac{4!}{4} = \frac{(4)(3)(2)(1)}{4} = 6

2! = \displaystyle \frac{3!}{3} = \frac{(3)(2)(1)}{(3)} = 2

1! = \displaystyle \frac{2!}{2} = \frac{(2)(1)}{(2)}

Now, we go to 0!

0! = \displaystyle \frac{1!}{1} = 1

As we can see from the 3 examples, 0! = 1.

 

 

8 comments , , ,

Introduction to Combinations

College Mathematics, Combinatorics, High School Algebra

Introduction to Combinations

In my Introduction to Permutations post, we have learned that the number of permutations (or arrangements) of n objects taken at n at a time written as P(n,n) is equal to n! = n(n-1)(n-2) \cdots (3)(2)(1), and we have also learned that the number of permutations of n objects taken k at a time written as P(n,k) is equal to \displaystyle\frac{n!}{(n - k)!}.

In Figure 1, shown are the permutations of 4 letters, A, B, C and D taken 4 at a time.  From the figure, we can see that there are indeed 4!= (4)(3)(2)(1) = 24 of such arrangement. In Figure 2, shown are the permutations of 4 letters taken 3 at a time, and we have shown that the number of permutations is equal to \displaystyle\frac{4!}{ (4 - 3)!} = \frac{4!}{1!} = (4)(3)(2)(1) = 24.  In Figure 3, we have again listed the permutations of 4 letters taken 2 at a time, and have shown that the number of permutations is equal to \displaystyle\frac{4!}{(4-2)!} =12.

Figure 1 – Permutations of ABCD, taken 4 at a time.

Figure 2 – Permutations of ABCD, taken 3 at a time.

Figure 3 – Permutations of ABCD, taken 2 at a time.

If we talk about combinations, however, the arrangement of objects does not matter. For example, if we want to buy a milk shake and we are allowed to choose to combine any 3 flavors from Apple, Banana, Cherry and Durian*, then the combination of Apple, Banana and Cherry is the same as the combination Cherry, Apple, Banana.

Try to list all the possible combinations of 3 flavors taken from 4 before proceeding.

If we choose to shorten the name the fruits by selecting the first letter of their names, we only have 4 possible combinations for question above: ABC, ABD, ACD, and BCD. Notice that these are the only possible combinations. Also, observe that if we list the permutations of ABC, we have ACB, BAC,BCA, CAB and CBA.  This means that in permutations, we have counted each combination of 3 flavors from 4 flavors 6 times (or 3! times instead of one.

In other words, a combination is just like a subgroup of a group. For instance, if we want to find the number of subgroups containing 3 objects taken from 4 objects (or the combination of 4 objects taken 3 at a time), it is the same as asking  “how many possible groups of 3 objects can be taken from 4 objects?” In Figure 4, all the possible subgroups of 3 letters taken from 4 letters are displayed by the orange border. You also would have realized that the number of permutations is an overcounting of the number of combinations.

Figure 4 – The combinations of 4 objects taken 3 at a time is the same as the number of subgroups of 3 objects taken from 4 objects.

In Figure 2, ABC, ACB, BAC, BCA, CAB and CBA are permutations of Apples, Banana and Cherry. For each subgroup of 3, we realized that we counted 3! = 6 times. So, to get the number of combinations, we divide our number of permutations P(4,3) by the number of permutations of our subgroupP(3,3) = 3!. Therefore, we can say that the number of combinations of 4 objects taken 3 at a time is equal to

\displaystyle\frac{P(4,3)}{P(3,3)} = \frac{\frac{4!}{(4-3)!}}{3!} = \frac {4!}{(4-3)! 3!}

In general, to get the number of combinations of n objects taken k at a time, we have to divide the number of permutations of P(n,k) by the number of permutations of the subgroup P(k,k).

\displaystyle\frac{P(n,k)}{P(k,k)} = \frac{\frac{n!}{(n-k)!}}{n!} = \frac {n!}{(n-k)! k!}

The combinations of n objects taken k is usually denoted by C(n,k) or \displaystyle n \choose k

_____________________________________________________________

*Durian is a fruit which can be found in the Philippines. It looks like a jackfruit.

Leave a comment , , , ,
1 2 3