Math 30P Fundamental Counting Principle Permutations Combinations Pathways and Pascal's Triangle Binomial Theorem Probability Problems

Fundamental Counting Principle: the principle for determining the number of ways two or more operations can be performed together

factorial notation: the notation, n!, used to represent the product of the first n natural numbers. n! is read as “n factorial.”

permutation: an arrangement of all or part of a set of objects, where the order of the arrangement is important

combination: a selection of all or part of a set of objects, where the order of the selection is not important. Form is nCr.

If you have gone shopping for clothes with friends or family, you have probably had to wait patiently until they made a decision as to what to purchase. To help customers make up their minds, salesclerks lay out a couple of pairs of pants and several shirts. This way, customers can quickly make comparisons and select the preferred combination.

In mathematics, a selection from a set of objects is also called a combination. When a selection is made, the order in which the elements are chosen is not important. The same would be true, for example, when choosing a shirt and pants combination. It doesn’t matter which item you buy first; what is important is the final look of the outfit.

permutation: an arrangement of all or part of a set of objects, where the order of the arrangement is important. Form is nPr.

Note: nPr = nCr × r!.

There are r! times as many permutations as combinations because there are r! ways of arranging the the r objects once they are chosen.

The permutation nPr represents two tasks: selecting r objects from a set of n objects first, then arranging the r objects selected. Using the Fundamental Counting Principle,

Equivalent Combinations: If two combinations have the same n value and the sum of their r-values is equal to n, then the two combinations are equal. Examples:

When you choose 2 objects from 10, there are are 8 left. This is the same as selecting 8 objects from 10 and having 2 left.

Use factorial notation to show that 10C2 = 10C8

### Example 1:

Determining the number of ways a selection from a set can be made when the order does not matter.

A customer is trying to decide between 2 different pairs of pants and 6 different shirts. How many combinations of 1 pair of pants and 1 shirt are possible?

### Solution

Use a tree diagram to illustrate the possible selections. In the diagram, use P1 and P2 to represent the pants and S1, S2, S3, S4, S5, and S6 to represent the shirts.

Using the Fundamental Counting Principle, 2 × 6 = 12 outfits are possible.

### Example 2

Determining the number of ways a selection from a set can be made when the order does matter.

A tray contains 4 different cookies.

a. How many ways can you select and arrange 3 cookies from the tray?

b. How many ways can you select 3 cookies from the tray if order doesn’t matter? c. How are the answers to questions a. and b. related?

### Solution

Order is important. Therefore, this is a permutation of 4 objects taken 3 at a time.

There are 24 ways of selecting and arranging three cookies from the tray.

### Solution

Let the set {A, B, C, D} represent the cookies on the tray.

The three-cookie combinations are {A, B, C}, {A, B, D}, {A, C, D}, and {B, C, D}.

There are 4 ways of selecting three cookies from the tray if order does not matter.

### Solution

The symbol used to represent the number of combinations is 4C3, which is read “4 choose 3.” This implies, “From 4, choose 3.” Here, 4C3 = 4.

The answers to questions a. and b. were 24 and 4 respectively.

Notice that 4P3 = 4C3 × 6 or 4C3 × 3!.

There are 6 or 3! times as many permutations as combinations because there are 3! ways of arranging the three cookies once they are chosen.

The permutation nPr represents two tasks: selecting r objects from a set of n objects first, then arranging the r objects selected. Using the Fundamental Counting Principle,

### Example 3

How many different 3-member committees can be selected from a class of 20 students?

### Solution

Order is not important; so, determine the number of combinations.

 Method 1: Using Pencil and Paper Method 2: Using a Graphing Calculator There are 1140 different committees that can be selected. There are 1140 different committees that can be selected

### Example 4

A cookie jar contains 5 cookies. How many ways can a child choose all 5 cookies if order doesn’t matter?

A cookie jar contains 5 cookies. A child is offered a cookie, but refuses. How many ways can this be done?

### Solution

Because the order doesn’t matter, determine the number of combinations.

If order is not important, the child can choose all five cookies only 1 way!

### Solution

There is only 1 way the child can reject the cookie. This is done simply by saying, “No.”

### Example 5

A Pure Mathematics 30 class has 10 boys and 12 girls. The teacher wants to form a committee of 3 students to plan the year-end picnic. Determine the number of committees possible if

There are no restrictions

There are no boys on the committee There must be at least one boy on the committee

### Solution

Without restrictions, there are 1540 committees possible.

### Solution

Because there are no boys on the committee, you must select committee members from the 12 girls.

There are 220 possible committees of only girls.

### Solution

Method 1: Considering All Possible Cases

Case 1: 1 Boy and 2 Girls

Because there are 10 boys and 12 girls to choose from, apply the Fundamental Counting Principle.

Case 2: 2 Boys and 1 Girl

Applying the Fundamental Counting Principle,

Case 3: 3 Boys

There are 1320 possible committees with at least one boy.

Method 2: Using an Indirect Approach

From the answer to question a., you know there are 1540 committees possible when there are no restrictions. Some of these committees will be all boys, others will be all girls, and the rest will be boys and girls. From the answer to question b., you know there are 220 committees that consist of only girls.

There are 1320 possible committees with at least one boy.

### Example 6

How many diagonals are there in a regular octagon?

How many diagonals are in a regular polygon with 20 sides? How many triangles can be formed by joining the vertices of a regular polygon with 20 sides?

### Solution

A regular octagon has 8 sides and 8 vertices. Choose any two vertices and join them. The line segment formed is either a side or a diagonal. The total number of ways of joining the 8 vertices is 8C2.

The number of diagonals of any regular polygon with n sides can be determined using the following equation:

Number of diagonals = nC2 - n

### Example 7

If 3(nC2) = 30 solve for n. Remember that for nCr, n r.

If nC3 = 3(nP2) solve for n. Remember that for nCr, n r.

### Solution

Because nC2 is only defined when n 2, where n is a whole number, n = 5.

Remember that for nCr, n r.

### Example 8

All the possible two-number permutations and combinations from {1, 2, 3, 4, 5}.

All the possible three-number permutations and combinations from {1, 2, 3, 4, 5}.

### Solution

The number of permutations of two numbers from {1, 2, 3, 4, 5} with no repetitions is

Each of the combinations in this question can be arranged in two ways.

The second list has double the number of pairs compared to the first list.

Notice that 2 = 2!

### Solution

The number of permutations of two numbers from {1, 2, 3, 4, 5} with no repetitions is 5P3 = 5 × 4 × 3 = 60

There are 3! or 6 times as many permutations as combinations.

Order is important with permutations, but not with combinations.

Notice that 6 = 3!

5C3 = 5P3 / 3! = 60 / 6 = 10

### Example 9

There are six colours: red, white, blue, green, yellow, and black. Find the number of two-colour combinations.

There are six colours: red, white, blue, green, yellow, and black. Find the number of three-colour combinations.

### Solution

There are six colours: red, white, blue, green, yellow, and black.

There are 15 two-colour combinations.

### Solution

There are six colours: red, white, blue, green, yellow, and black.

n = 6 and r = 3

There are 20 three-colour combinations.

The history of combinatorics and probability is imbedded in games of chance; therefore, many examples and questions on the diploma examination involve a standard deck of cards. If you are not familiar with what a standard deck of cards is made up of, read on.

A standard deck consists of 52 cards divided into 4 suits: clubs, spades, hearts, and diamonds.

Each suit has 13 cards: 1 ace, 9 numbered cards (from 2 to 10), and 3 face cards (jack, queen, and king).

### Example 10

How many 13 card hands can be made from a deck of 52 cards?

Bridge hands have 13 card hands. How many bridge hands can be made with 4 aces? How many bridge hands can be made with no aces?

### Solution

There are approximately 1.93 × 1011 different hands with no aces.

### Example 11

How many 5 card hands can be made from a deck of 52 cards?

How many 5 card hands with only red cards can be made from a deck of 52 cards? How many 5 card hands can be made of the same suit?

### Solution

There are 2 598 960 different five-card hands.

There are 52 ÷ 2 = 26 red cards in a deck of cards.

### Solution

There are 65 780 different five-card hands containing only red cards

### Solution

There are 4 suits in a standard deck of cards; therefore, there are 52 ÷ 4 = 13 cards in each suit.

You need to determine the number of different hands containing all cards of the same suit among the 4 different suits.

There are 5148 different five-card hands containing all cards of the same suit.

### Example 12

How many distinct 5 card hands can be made from a deck of 52 cards with:

only 1 queen and 3 kings 3 red cards and 2 black cards?

### We must use the fundamental counting principle and combinations:

13C3 × 13C2 = 286 × 78

= 22308

There are 22 308 different five-card hands.

### We must use the fundamental counting principle and combinations:

4C1 × 4C3 × 48C1= 4 × 4 × 48

= 768

There are 768 different five-card hands containing 1 queen and 3 kings

### Solution

There are 52 ÷ 2 = 26 red cards in a deck of cards.

There are 52 ÷ 2 = 26 black cards in a deck of cards.

We must use the fundamental counting principle and combinations:

26C3 × 26C2 = ×

=

There are different five-card hands containing 3 red and 2 black cards.

### Example 13

How many distinct 5 card hands can be made from a deck of 52 cards with:

no fives?

4 aces? only 3 face cards?

### We must use the fundamental counting principle and combinations:

4C0 × 48C5 = 1 × 1712304

= 1712304

There 1 712 304 are different five-card hands with no fives.

### We must use the fundamental counting principle and combinations:

4C4 × 48C1 = 1 × 48

= 48

There are 48 different five-card hands with 4 aces.

### Solution

We must use the fundamental counting principle and combinations:

There are 4(3) = 12 face cards in a deck of cards.

12C3 × 40C2 = 220 × 780

= 171600

There are 171 600 different five-card hands containing only 3 face cards.

Parts of this work has been adapted from a Math 30 Pure learning resource originally produced and owned by Alberta Education

Comments to:  Jim Reed - Homepage