9.6 Counting Principles

Simple Counting Problems

• Counting the number of ways an event can occur is important, because it necessary in order to understand probability. 
• The easiest way to solve simple counting problems is to list each possible way that an event can occur. 

The Fundamental Counting Principle 

Some events can occur in so many different ways that it is not feasible to write out the entire list. In such cases, you must use formulas and counting principles. The most important of these is the Fundamental Counting Principle.

Fundamental Counting Principle 

• Let E₁ and E₂ be two events. The first event E₁ can occur in m₁ different ways. After E₁ has occurred, E₂ can occur in m₂ different ways. The number of ways that the two events can occur is 
  
• The Fundamental Counting Principle can be extended to three or more events. For instance, the number of ways that three events E₁, E₂, and E₃ can occur is 
  
   

Example: Using the Fundamental Counting Principle 

At an ice cream store, there are 11 ice cream flavors. There are 7 options for toppings. Additionally, there are 3 colors of spoons available. How many total choices are there?

Total choices =

Thus, there are 231 total choices. 

Permutations 

You can use the Fundamental Counting Principle to determine the number of ways that n elements can be arranged in order. An ordering of n elements is called a permutation of the elements.

Definition of Permutation

• A permutation of n different elements is an ordering of the elements such that one element is first, one is second, one is third, and so on.   

Number of Permutations of n Elements 

• The number of permutations of n elements is

• In other words, there are n! different ways that n elements can be ordered. 

                                                                                 

Example: Finding the Number of Permutations of n Elements 

How many permutations are possible for the letters S, T, A, and R?

Consider the following reasoning:

First position: Any of the four letters
Second position: Any of the remaining three letters
Third position: Either of the remaining two letters
Fourth position: The one remaining letter

The total number of permutations of the six letters is

Occasionally, you are interested in ordering a subset of a collection of elements rather than the entire collection. For example, you might want to choose (and order) r elements out of a collection of n elements. Such an ordering is called a permutation of n elements taken r at a time.

Permutations of n Elements Taken r at a Time

• The number of permutations of n elements taken r at a time is 
  

Example: Permutations of n Elements Taken r at a Time

Ten people are competing in a swim meet. In how many different ways can these people come in first, second, and third. (Assume that there are no ties.)

In this problem, you are trying to find the number of permutations of ten people taken three at a time. One can successfully accomplish this by using the formula for the number of permutations of n elements taken r at a time.

Step 1:

Step 2:

Step 3: 

Step 4: 

There are 720 different ways the ten people can come in first, second, and third.

Distinguishable Permutations 

Suppose a set of n objects has n₁ of one kind of object, n₂ of a second kind, n₃ of a third kind, and so on, with 

The number of distinguishable permutations of the n objects is 

  

Combinations

Now, we will discuss a method of selecting subsets of a larger set in which order is not important. Such subsets are called combinations of n elements taken r at a time.

Combinations of n Elements Taken r at a Time

The number of combinations of n elements taken r at a time is

  




Example: Combinations of n Elements Taken r at a Time

Seven slips of paper with the letters N, G, S, F, R, T, C written on them are put into a hat. The letters stand for Nicholas, George, Stephanie, Felicia, Rose, Tessa, and Carly, respectively, and they represent seven people who have been entered to win a brand new flat screen television. Three winners will be chosen. In how many different ways can three letters be chosen from the letters on the slips of paper if the order of the three letters is not important?

In this problem, you are trying to find the number of combinations of seven people taken three at a time. One can successfully accomplish this by using the formula for the number of combinations of n elements taken r at a time.

Step 1:

Step 2:

Step 3: 

Step 4:

There are 35 combinations.

9.4 Mathematical Induction

mathematical induction - means of proving a theorem by showing that if it is true of any particular case, it is true of the next case in a series, and then showing that it is indeed true in one particular case

Steps to Mathematical Induction:

Let P(n) be a statement involving the positive integer n.

1.) Show that P(1) is true.

2.) Assume P(n) is true for n.

3.) Show that is is true for n+1.

 

Example

P(n) = 1 + 3 + 5 + 7 +...+ (2n-1) = n^2

Step 1: Show it is true for n=1.

P(1) = 1 = 1^2
          1 = 1 ✓

Step 2:  Assume P(n) is true.

P(n) = 1 + 3 + 5 + 7 +...+ (2n-1) = n^2 

Step 3: Show it is true for n+1.

1 +3 + 5 + 7 +...+ (2n-1) + [2(n+1) - 1] = (n+1)^2 
                                     n^2 + 2n + 1 = n^2 + 2n + 1  ✓

*Since 1 + 3 + 5 + 7 +...+ (2n-1) = n^2, you can substitute 1 +3 + 5 + 7 +...+ (2n-1)  for n^2*

9.2 Arithmetic Sequences and Partial Sums

This section covers:

• How to find the nth terms of arithmetic sequences
• How to find the sums of arithmetic sequences

       Arithmetic Sequences

A sequence of terms is considered arithmetic if the differences between consecutive terms are the same.

The following sequence:
         a₁, a₂, a₃, a₄, ..., a_n, ...
is arithmetic if there is a number d such that a₂ - a₁ = a₃ - a₂ = a₄ - a₃ = ... = d.

The number d is the common difference of the arithmetic sequence.

An example of an arithmetic sequence is:
         3, 7, 11, 15, 19, ...
because:
         7 - 3 = 4
         11 - 7 = 4
         15 - 11 = 4
         19 - 15 = 4
In this case, d, the common difference, is 4.

The nth term of an arithmetic sequence has the form:
         a_n = a₁ + d(n - 1).

For example:

In the sequence -1, 12, 25, 38, 51, where -1 = a₂, find the 9th term in the sequence.
         a₉ = a₁ + d(n - 1)
         12 - (-1) = 13, so d = 13.
         a₂ - d = a₁
         -1 - 13 = -14 = a₁
         a₉ = (-14) + 13(9 - 1)
         a₉ =  90.In this sequence, the 9th term is 90.

If you know the nth term of an arithmetic sequence and you know the common difference of the sequence, you can find the (n+1)th term by using the recursive formula:
         a_n+1 = a_n + d
              or
         a_n = a₁ + (n-1)d


       Sums and Partial Sums

The sum of a finite arithmetic sequence with n terms is: S_n = ⁿ/₂(a₁ + a_n).
For example:

In a sequence of 7 terms where a₁ = 56, d = 23, and a₇ = 194, find the sum of the sequence.
S_n = ⁿ/₂(a₁ + a_n)
S₇ = ⁷/₂(56+194)
S₇ = 875

The sum of the first n terms of an infinite sequence is called the nth partial sum.

5.5 Double-Angle Formulas

The double-angle formulas are some of the most commonly used and most important trigonometric identities. These are the formulas and how to derive them:

To derive the sine formula, you can use a sum formula:

To derive the cosine formulas, follow a similar process: 

The above formula is also equivalent to this: 

Simplifying, you get

You can also change the first formula to this:

Again, simplify:

To derive the tangent formula, use a sum formula:

Examples:

Solving a Double-Angle Equation

Find all solutions to the following equation on the interval 

1) Begin by using a double-angle formula for cosine:

2) Next, factor.

3) Set the factors equal to zero and simplify.

    

4) Solve for x on the given interval.

    

Using Double-Angle Formulas in Sketching Graphs

Graph the following function over the interval  

1) First, factor out a 2.

2) Then, you can substitute using a double-angle formula.

From this equation, we know that the amplitude of the graph is 2, and the period is .

Using this information, we can sketch the graph: 

Evaluating Functions Involving Double Angles

Use the following to find .

     

1) From the given information, you can draw a triangle like this:

2) Next, you use the double-angle formula, substitute in the known values, and simplify.