Section 12.1: Permutations

12.1 Outline

  1. 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
  2. Factorial
    1. definition
    2. multiplication property of factorials
    3. count-down property
    4. permutation formula
  3. 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.

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.

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

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 ) !