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

Revision as of 14:55, 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 takes too long and it is necessary to formulate and generalize counting methods.

Preliminaries

Let us begin with a couple basic concepts. Imagine the first ten integers. How many ways can you arrange these integers in a line?

There are ten options for the first number in the arrangement. Now, whatever number you choose to be the first number, there will be nine remaining numbers to set as the second number in the arrangement. And whatever number you choose, there will be eight remaining numbers for the third number and so on. In total, 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 arranging all of the numbers, we take only six of the numbers and arrange them. 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 way to choose a subset of a set. Let us denote the number of ways to choose a subset of size k from a set of size n as $ C^n_k $. You may notice that for these k objects, there are k! ways to order them. 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.

Examples

Q: In the United States, there are 50 states. Suppose a company wants to build 15 distribution centers around the US, 5 major centers and 10 minor centers. Further suppose that every state cannot have more than one center. How many ways to place the distribution centers?

A: We can think of this as a partition into 3 sets. A set of 5 states with major distribution centers, a set of 10 states with minor distribution centers, and 35 states without centers. Thus, the number of ways is

$ {50 \choose 35,10,5} = \frac{50!}{35! 10! 5!} $

Q: A landscaping company has 6 employees (as in the introduction). How many ways to divide the employees into two teams?

A: This is a partition of a set of size 6 into two indistinguishable subsets of size 3. Thus, we calculate the usual number of partitions and then divide by 2! to account for the two indistinguishable sets. So the number of divisions is,

$ \frac{1}{2!} \times {6 \choose 3,3} = \frac{6!}{2! 3! 3!} = \frac{720}{72} = 10 $

Q: A basketball camp has 30 players. The administration wishes to divide the players into 6 teams of 5 players. How many ways are there to do this?

A: This is a partition problem with 6 subsets of 5. Further, we must divide by 6! to account for the 6 teams being indistinguishable. So the number of ways is,

$ \frac{1}{6!} \times {30 \choose 5,5,5,5,5,5} = \frac{30!}{6! (5!)^6} $

Partitions of Sets into Any Size

Suppose we generalize the partition methods by allowing multiple sizes of subsets. In these cases, we can always divide the problem up into separate cases where the partitions have fixed sizes, using the previous methods on each of these cases, then adding up the results.

However, there is a simpler way of calculating all possible subsets of a set. There are $ j^n $ ways to divide a set of size n into j subsets. We can see this in the following way. For each object, there are j subsets that it can be assigned to. There are n objects so we multiply j options repeatedly n times yielding the general formula.

Examples

Q:A organization is giving away 12 artistically designed (distinguishable) vases to its officers. It will be sending some to the marketing department, some to the research department, and some to the production department. Each department can have any number of vases. How many ways are there to divide the vases among the recipients?

A: This is a problem of dividing 12 objects into 3 subsets of any size. Thus, the number of ways to divide the vases are,

$ 3^{12} $

Q: An art class has 20 students. The teacher has bought materials for 5 different art projects, one of which is a gold leaf project. The teacher doesn't mind if some of the projects have many or no students working on them except the teacher wants at least one student to work on the gold leaf project to prevent the gold from going to waste. How many ways are there for the students to be divided among the projects?

A: We can calculate the total number of ways to divide the students without the gold leaf condition and then subtract the number of ways that involve no one working on the gold leaf. The first number is dividing 20 objects into 5 subsets of any size, and the second number is dividing 20 objects into 4 subsets of any size (the 4 projects that aren't the gold leaf project). Thus, the number of ways is,

$ 5^{20} - 4^{20} $