Section 12.1: Permutations

12.1 Outline

A. Election problem
     1. tree diagram
     2. fundamental counting principle
     3. arrangement
     4. ordered pair/ordered triple
     5. define permutation
     6. notation for permutations
     7. evaluating permutations
B. Factorial
     1. definition
     2. multiplication property of factorials
     3. count-down property
     4. permutation formula
C. Distinguishable permutations
     1. indistinguishable items
     2. distinguishable items
     3. formula for distinguishable permutations

12.1 Essential Ideas

Fundamental Counting Principle

If one task can be performed in m ways, and if, after that task is completed, a second task can be performed in n ways, then the total number of ways of ways for both tasks is found by multiplication: mn.

Permutations

A permutation of r elements selected from a set of n elements is an ordered arrangement of those r elements selected without repetitions. The order of selection is important.

Counting Formulas

Factorial: n! = n(n - 1)(n - 2)(n - 3) ... (3)(2)(1).

Count-down formula: n! = n(n - 1)!

Permutation formula: The number of ways of selecting r elements from a set with cardinality n in which the order of section is important is n!/(n - r)!

Number of distinguishable permutations:
If n objects are partitioned so that there are n₁ of one kind, n₂ of another, and n₃ of still a third kind (so that n₁ + n₂ + n₃ = n), then the number of ways that the n objects can be selected is n! divided by the product of (n₁)!(n₂)!(n₃)!.