MDM4U Special Combinatorics 2016-02-29


We spent some time on a few more problems today. You already had the skills to solve them, but I wanted to present a different perspective.

One problem was the following:

Example 1

Mr. Grasley has 5 different varieties of tea at home. He can bring any of them to work with him. How many different combinations of tea could he bring?

Solution 1

Using combinations, we can count separate cases depending on the number of varieties he brings.

5 varieties: \binom{5}{5}=1

4 varieties: \binom{5}{4}=5

3 varieties: \binom{5}{3}=10

2 varieties: \binom{5}{2}=10

1 varieties: \binom{5}{1}=5

0 varieties: \binom{5}{0}=1

Summing these we get 32 different combinations, including the case in which he brings no tea to work.

Solution 2

Instead of counting each case separately, we can instead realize that Mr. Grasley has to make 5 choices: for each variety of tea, he must decide whether to bring it to work or leave it at home. Using the Fundamental Counting Principle, there are

2\times2\times2\times2\times2=2^5=32

different combinations of choices.

In general

When we are counting all of the combinations of n distinct items, we have

\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+\dots+\binom{n}{n}=2^n

Example 2

We also looked at counting divisors. Every whole number is made up of a unique prime factorization, and all of its divisors are the products of combinations of those factors.

For example, let’s consider the number 1960. Rewriting it as a product of primes we have

1960 = 2^3 \times 5 \times 7^2

To create a divisor, we must choose how many “copies” of each prime factor to include. For 2, there are four possibilities: 0, 1, 2, and 3 “copies”, corresponding to the numbers 2^0 2^1 2^2 , and 2^3 . Similarly there are two possibilities for 5, and three possibilities for 7. This yields 4 \times 2 \times 3 = 24 different divisors for 1960. This includes the case 2^0 \times 5^0 \times 7^0=1 .

Homework

Page 287 #6, 11, 12, 13.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s