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.