Possibility Trees and the Multiplication Rule: Permutations

Given the set {a, b, c}, there are six ways to select two letters from the set and write them in order.

ab ac ba bc ca cb

Each such ordering of two elements of {a, b, c} is called a 2-permutation of {a, b, c}.

Definition: An r-permutation of a set of n elements is an ordered selection of r elements taken from the set of n elements. The number of r-permutations of a set of n elements is denoted P(n, r).

Theorem 6.2.3 If n and r are integers and 1 £ r £ n, then the number of r-permutations of a set of n elements is given by the formula

P(n, r) = n(n – 1)(n – 2)…(n – r + 1)

or, equivalently,

P(n, r) = n!/(n – r )!.

Exercise 16, page 293. keypad

  1. How many different PINs are represented by the same sequence of keys as 2133?
  2. How many different PINs are represented by the same sequence of keys as 6809?
  3. At an automatic teller machine, each PIN corresponds to a four-digit numeric sequence. How many such numeric sequences contain no repeated digit?
  4. Consider the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, how many 4-permutations are there?
  5. What is the probability that a randomly chosen PIN will not have a repeated digit?

Solution

  1. Step one: choose one of 4, {2, A, B, C}. Step two: choose one of 3, {1, Q, Z}. Step three: choose one of 4, {3, D, E, F}. Step four: chose one of 4, {3, D, E, F} (although we have already used a 3 in step 3, this is only one of the four choices and the original number 2133 has to be counted.) So by the multiplication rule there are 4(3)(4)(4) = 192 different PINs represented by the sequence 2133.
  2. Step one: choose one of 4. Step two: choose one of 4. Step three: choose one of 1. Step four: chose one of 4. So by the multiplication rule there are 4(4)(1)(4) = 64 different PINs keyed by the sequence 6809.
  3. Consider the four step process: 10(9)(8)(7) = 5040 PINs with no repeated digit.
  4. P(10, 4) = 10! / (10 – 4)! = 10! / 6! = 10(9)(8)(7) = 5040.
  5. P(E) = |E| / |S| = 5040 / 104 = 50.4%

 

Some additional links:
http://regentsprep.org/Regents/math/permut/Lperm.htm
http://regentsprep.org/Regents/math/permut/LpermRep.htm