Example 1

How many ways can six boys and three girls be seated in a row if the girls all have to sit together?

This question is similar to ones that we saw in the last section where we treated an empty seat as a "person" for purposes of counting. In this case, we'll treat the group of girls as a single block.

If we treat the girls as a single unit then we need to put seven "people" into seven slots. Following the approach we took in the last section, that gives us this arrangement:

7

6

5

4

3

2

1

If we multiply those numbers together, we get 7 · 6 · 4 · 3 · 2 · 1 = 5,040 possible arrangements.

At this point, some of you may be concerned about the group of girls. There are multiple ways that the girls can be seated within their group and we need to take that into consideration. Since there are three girls there are 3 · 2 · 1 = 6 ways that the girls can be arranged within their block. Since the arrangement of the girls and the arrangement of the boys around them on the row are independent of each other, we can apply the Multiplication Principle to conclude that there are a total of 6 · 5040 = 30240 total arrangements.

Example 3

How many ways can five people be selected for a committe of three?

At first glance this looks like a straightforward example of what we've been doing. Five people can have the first position, four the second and three the third for a total of 5 · 4 · 3 = 60 arrangements. But there's a problem.

There is no order within the committee. For example, suppose three of the people are named "Alice", "Bill" and "Cindy". Our counting method counts "Alice", "Bill" and "Cindy" as one arrangement and "Bill", "Alice" and "Cindy" as a different one. Our problem is that both of those arrangements represent the same committee so we don't want to count them separately.

The Multiplication Principle will come to our rescue here. Let x be the number of committees, i.e. the number where the order of the names doesn't matter. Since there are three people on each committee, we know that there are a total of 3 · 2 · 1 = 6 arrangements of the members within each committee. According to the Multiplication Principle:

(number of unordered arrangements) · (number of arrangements within a group) = (number of ordered arrangements)

If we substitute our numbers into that equation we get:

x · 6 = 60

So the number of committees (remember that that's our x) must be 60 / 6 = 10.

This sort of arrangements where the order doesn't matter is called a "combination". We'll talk more about this in the next section.

Example 2

Suppose a set has 5 elements. How many subsets does the set have?

First, let me clarify the question by giving an example. Suppose A = {1, 2, 3, 4, 5}. A subset of A is any combination of the numbers in A without repetition. So, for example, {1, 2, 4}, {1} and {1, 2, 3, 4, 5} would all be subsets of A.

For a given subset, the question we nee to ask is, "For each of the five elements in A, is that element in the set or isn't it?" The last part of that sentence is the key: For each of the five numbers, there are exactly two possibilities. Either it's in a given subset or it isn't. So our diagram will have five slots, one for each digit.

And for each digit, there are two possibilities.

2

2

2

2

2

Multiplying out those numbers gives us 2⁵ = 32 possible subsets.

Example 4

How many subsets does a set with n elemens have?

This is a natural extension of Example 2. (It's also a classic question from set theory.) We'll start off with n spots to fille.

		...
1	2		n - 1	n

Just like in Exaple 2, there are 2 possibilities for each slot. Either that element is in the subset or it isn't.

2	2	...	2	2
1	2		n - 1	n

Multiplying those numbers together means multiplying 2 by itself n times which, in exponential notation, is 2ⁿ.