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.3 - Geometric Sequences

Geometric Sequences are sequences that have a common ratio (r).

Or...

A simple form of a Geometric Sequence

A popular example is

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ...

Every consecutive term is 2 times the preceding term.

In this particular sequence, a=1 and r=2

The Sum of a Finite Geometric Sequence can be defined under this equation:

If you were to plug in the previous sequence you'd get:

And, finally, the Sum of an Infinite Geometric Sequence

IMPORTANT:  This formula only works if  | r | < 1

The formula is simply:

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.

Section 9.1 Sequences, Series, and Probability part 2

In this section we will discuss summation notation.
              Summation notation is also known as sigma notation because it involves the use of the upper               case Greek letter sigma, written as .

Definition of Summation Notation

          i is the index of summation
          n is the upper limit of summation
          1 is the lower limit of summation
               
                  Example:

Properties of Sums

1. c is any constant

2.

3. 

Series

An infinite series or simply a series involves the sum of the terms of an infinite sequence.

Definition of a series

              Consider the infinite sequence

              1. The sum of all terms of the infinite sequence is called an infinite series and is denoted by                                                     

              2. The sum of the first n terms of the sequence is calls a finite series or the nth partial sum                                     and is denoted by.

Example

              The 3rd partial sum of.

              The sum of the series is