Chapter 4
Counting Techniques


 
 
1.  Tree Diagrams

Why construct tree diagrams?

A.  Lists all possibilities of a sequence of events in a systematic way

B.  Helps eliminate omission of possible outcomes

 


 
2.  Multiplication Rules for Counting: used when we’re interested in the total number of possible outcomes, but not in listing each and every one.....


A.  Rule 1 - In a sequence of n events, in which the first event has k1 possibilities (choices), the second event has k2 possibilities, and so on, the total number of possibilities in the sequence is given by:
 
 

Total = (k1 )(k2 )(k3 )...(kn )



The "kn" is "k subscript n" or "k sub n"


B.  Rule 2 - If each event in a sequence of n events has k possibilities (choices), then the total number of possibilities in the sequence will be:

Total = (k)(k)(k)...(k) = k^n

(or just simply "k to the power of n")


Often, in computers, when we say "k ^ n", the "^" means superscript.
 

 

3.  Permutations:  Different combinations of any number of quantities, where order is important.

REMEMBER THIS LAST PART - IT IS CRITICAL FOR YOUR TESTS!!! IF I GIVE YOU A QUESTION, AND THE QUESTION SAYS SOMETHING LIKE "they must be arranged in a certain pattern", or something like that, then IT IS A PERMUTATION! THIS IS A POINT WHERE ALMOST EVERYONE GETS CONFUSED! 

But before we go further...some algebra review (but I thought this was STATISTICS?!?)!
 
Factorials:  (See Appendix A of the text for more info)

Mathematical definition: n! = (n)(n-1)(n-2)...(3)(2)(1)

This is said as "n factorial"

 Example:     5! = (5)(4)(3)(2)(1) = 120

So......when said in English "five factorial equals 120"
 
 
Rules for factorials:

 Addition:  5! + 3! = {(5)(4)(3)(2)(1)} + {(3)(2)(1)} = 120 + 6 = 126

 Subtraction:  5! - 3! = {(5)(4)(3)(2)(1)} - {(3)(2)(1)} = 120 - 6 = 114

 Multiplication:  (5!)(3!) = {(5)(4)(3)(2)(1)}{(3)(2)(1)} = (120)(6) = 720

 Division:  (6!)/(3!) = {(6)(5)(4)(3)(2)(1)}/{(3)(2)(1)} = 720/6 = 120



Also, Note:  0! = 1

That's right: "zero factorial  equals one"
> This is true by definition. Just believe it - whenever you see "zero factorial", it is one. Also, there are no 'negative' factorials
 

OK, Now back to permutations.........
 
 

A.  Rule 1 - The number of permutations of n distinct objects when taken together is: 

n!

But what if you’re not going to use all the objects?
 
 
B.  Rule 2 - The arrangement of n objects in a specific order using r objects at a time is called “a permutation of n objects taken r objects at a time” and is given by:

nPr = n!/(n-r)!




>>>>>>>>>>>>The " nPr " is a symbol for permutation. 

But what if the objects are not all different?
 
C.  Rule 3 - The number of permutations of n objects in which k1 are alike, k2 are alike, and so on, is given by:

Total = (n!)/{(k1)(k2)(k3)...(kp)}



 
 
3.  Combinations - A selection of distinct objects without regard to order; use when order or arrangement is not important.


REMEMBER THIS LAST PART - IT IS CRITICAL FOR YOUR TESTS!!! IF I GIVE YOU A QUESTION, AND THE QUESTION SAYS SOMETHING LIKE "without regard to the specific arrangement", or something like that, then IT IS A COMBINATION! THIS IS DIFFERENT FROM THE PERMUTATION. It's another point where confusion takes place.

Combination Rule - The number of combinations of r objects selected from n objects is given by:

nCr = (n!)/{(n-r)!(r!)}

 


 
 
Homework:

No reading assignment. Go to Lesson 5. The Schaum's outlines will help in this part if the course (Chapter 6 of Schaum's outlines - see my comment in the syllabus).