ing ll First, we map this problem about chess pieces to a question about sequences. There is a bijection from configurations to sequences here rp, Tk, and ro are distinct rows and Cp, Ck, and cb are distinct columns. In particular, Tp is the pawn s row, cp is the pawn s column, Tk is the knight's row, etc. Now we can count the number of such sequences using the Generalized Product rule Tp is one of 8 rows p is one of 8 columns .Tk is one of 7 rows(any one but rp) Ck is one of 7 columns(any one but cp) .rb is one of 6 rows(any one but rp or rk Cb is one of 6 columns(any one but cp or Ck) Thus, the total number of configurations is (8.76) 1.3 Permutation A permutation of a set S is a sequence that contains every element of S exactly once. For example, here are all the permutations of the set a, b, cl (a, b, c)(a, c, b)(b, a, c) (b, c,a)(c,a, b)(c, b,a How many permutations of an n-element set are there? Well, there are n choices for the first element. For each of these, there are n-1 remaining choices for the second element For every combination of the first two elements, there are n-2 ways to choose the third element, and so forth Thus, there are a total of n·(n-1)·(n-2)…3·2.1=n! permutations of an n-element set. In particular, this formula says that there are 3!=6 permuations of the 3-element set a, b, c, which is the number we found above Permutations will come up again in this course approximately 1.6 bazillion times. In fact, permutations are the reason why factorial comes up so often and why we taught you Stirlings approximation m!4 Counting II First, we map this problem about chess pieces to a question about sequences. There is a bijection from configurations to sequences (rp, cp, rk, ck, rb, cb) where rp, rk, and rb are distinct rows and cp, ck, and cb are distinct columns. In particular, rp is the pawn’s row, cp is the pawn’s column, rk is the knight’s row, etc. Now we can count the number of such sequences using the Generalized Product Rule: • rp is one of 8 rows cp • is one of 8 columns • rk is one of 7 rows (any one but rp) • ck is one of 7 columns (any one but cp) • rb is one of 6 rows (any one but rp or rk) • cb is one of 6 columns (any one but cp or ck) Thus, the total number of configurations is (8 7 · 6)2 · . 1.3 Permutations A permutation of a set S is a sequence that contains every element of S exactly once. For example, here are all the permutations of the set {a, b, c}: (a, b, c) (a, c, b) (b, a, c) (b, c, a) (c, a, b) (c, b, a) How many permutations of an n­element set are there? Well, there are n choices for the first element. For each of these, there are n − 1 remaining choices for the second element. For every combination of the first two elements, there are n − 2 ways to choose the third element, and so forth. Thus, there are a total of n · (n − 1) · (n − 2) 3 2 1 = · · · · · n! permutations of an n­element set. In particular, this formula says that there are 3! = 6 permuations of the 3­element set {a, b, c}, which is the number we found above. Permutations will come up again in this course approximately 1.6 bazillion times. In fact, permutations are the reason why factorial comes up so often and why we taught you Stirling’s approximation: n n n! ∼ √ 2πn � � e