Difference between revisions of "Counting subsets of sets" - Rhea

Revision as of 08:42, 13 March 2013

In this tutorial, some counting methods will be discussed. In particular, counting the number of ways to form subsets of a larger set under various conditions.

Introduction

Suppose you own a landscaping company with six employees: Alice, Bob, Charlie, Dorothy, Evan, and Fred. To make managing easier, you decide to divide the six workers into two evenly sized teams. How many ways are there to do this?

As it turns out, there are ten ways to accomplish the division. Denoting the people by their initial, the ten ways are:

{A,B,C} {D,E,F}

{A,B,D} {C,E,F}

{A,B,E} {C,D,F}

{A,B,F} {C,D,E}

{A,C,D} {B,E,F}

{A,C,E} {B,D,F}

{A,C,F} {B,D,E}

{A,D,E} {B,C,F}

{A,D,F} {B,C,E}

{A,E,F} {B,C,D}

However, for problems on a larger scale, enumeration will not suffice and it becomes necessary to formulate and generalize counting methods.

Preliminaries

Let us begin with a couple basic concepts. Suppose you have the integers from 1 to 10 lined up in order. Next, you scramble and shuffle them into any order you wish. How many ways can you do this?

Well, any of the ten numbers can become the first number. So there are ten options for the first number in the new order. Now, whatever number you choose to be the first number, there will be nine remaining numbers to set as the second number in the new order. And whatever number you choose, there will be eight remaining numbers for the third number and so on. In this way, you will have 10 options for the first choice, 9 options for the second choice, 8 options for the third choice, all the way down to 1 option for the tenth choice. So the number of ways to scramble the ten numbers is

$ 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 10! $

This is known as counting permutations. In general, there are $ n! $ ways to permute $ n $ distinguishable objects.

However, we can generalize this concept. Suppose instead of taking the numbers and forming a new order, suppose we take only six numbers and make a new order from those three. Similar to the other case, there will be 10 options for the first choice, 9 options for the second choice, all the way down to 5 options for the sixth choice. So the number of ways to choose a new order with five numbers is

$ 10 \times 9 \times 8 \times 7 \times 6 \times 5 = \frac{10!}{4!} $

In general, there are

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

ways to choose k objects with order from a set of n distinguishable objects. Let us denote this as $ P^n_k $.

Finally, let us introduce the concept of a combination. A combination is a way to choose k objects without order from a set of n distinguishable objects and will be denoted as $ C^n_k $. You may notice that for these k objects, there are k! ways to order them. So since we can choose a combination of k objects and an ordering for those k objects and get a unique way to choose k objects with order. So,

$ C^n_k \times k! = P^n_k $

$ {n \choose k} := C^n_k = \frac{P^n_k}{k!} = \frac{n!}{(n-k)!k!} $

Examples

Q: How many ways are there to arrange the letters in the alphabet?

A: This is a permutation of a set with 26 distinguishable objects. So there are 26! ways. (You can compute this with a calculator if you wish but we will leave it in this simplified form.)

Q: An Olympic race has 100 contestants. How many ways to give gold, silver, and bronze medals?

A: This is choosing 3 objects with order from a set of 100 objects. So the number of ways is,

$ P^{100}_3 = \frac{100!}{97!} = 970200 $

Q: A wealthy car manufacturer is writing her will. She has 3 different cars and 100 grandchildren. She won't give multiple cars to one grandchild. How many ways are there to give the cars away in her will?

A: We can think of this problem as selecting 3 grandchildren with order from the set of 100 grandchildren, then giving the first selected grandchild the first car, and so on. Thus, the number of ways is,

$ P^{100}_3 = \frac{100!}{97!} = 970200 $

Q: A town security system has 10 security shifts available and 22 applicants. How many ways to hire for the 10 different positions?

A: Once again, we think of selecting 10 people with order from the 22 applicants and giving the first person the first shift and so on. So the number of ways is,

$ P^{20}_{10} = \frac{22!}{12!} $

Q: The Omaha Zoo is hiring 12 zookeepers. They have 300 applicants. How many ways to hire 12 zookeepers from the applicants?

A: We would use combinations in this case since hired people are indistinguishable. In other words, the order of the hiring doesn't matter. So, the number of ways is,

$ {300 \choose 12} = \frac{300!}{12! \times 288!} $

Partitions Of Sets into Fixed Sizes

In the last section, the concept of a combination was introduced. You may notice that a combination is the same as a partition of a set. For instance, choosing 12 zookeepers from 300 applicants is the same as partitioning the set of 300 applicants into a set of 12 zookeepers and set of 288 rejects.

Let us generalize this concept. Suppose we have 30 zookeepers and we want 8 to work with the Elephants, 12 to work with the Giraffes, and 10 to work with the Penguins. How many ways to distribute the 30 zookeepers among these three tasks? Well suppose there are x ways to distribute them. Once we have a distribution, we could order the Elephant people (8! ways) and put them first, order the Giraffe people (12! ways) and put them second, and then order the Penguin people (10! ways) and put them last. In this way, we will have a unique permutation. So,

$ x \times 8! \times 12! \times 10! = 30! $

$ x = \frac{30!}{8! 12! 10!} = {30 \choose 8,12,10} $

In general, the number of ways to partition a set of n objects into j distinguishable subsets with sizes $ k_1, k_2, ..., k_j $, is

$ { n \choose k_1,k_2,...,k_j} = \frac{n!}{k_1! k_2! ... k_j!} $

There is a complication if the subsets are not all distinguishable. However, this is easily remedied. For instance, if three of the subsets are indistinguishable we must divide by 3! to avoid overcounting where the order doesn't matter. If two pairs of the subsets are indistinguishable we must divide by 2! twice to avoid overcounting the where the order doesn't matter. This concept will be further illustrated in the examples.