Topics Covered on Exam 1
  1. Net Diagrams
    1. How they work, tracing from top to bottom to create a permutation
    2. The simple theorems from the first few classes
      1. A line can be placed at the bottom to force an element to land at the last position
      2. More generally, given any element at the top, any position at the bottom and any level, a horizontal line may be placed at that level so that the given element ends up at the assigned position.
      3. If a permutation has k elements out of place relative to home position, then any net diagram generating that permutation needs at least k/2 rungs.
      4. No more than n - 1 rungs are ever needed to generate a permutation on n elements.
    3. The minimum number of rungs needed to create a k-cycle is k - 1
    4. And therefore, to compute the minimum number of rungs needed in a net diagram to generate a given permutation, on simply adds together (Size - 1) for the various sizes of the cycles in the permutation.  Thus, to generate the permutation (1234)(567)(89), we would add (4-1) + (3-1) + (2-1) = 6, and conclude that six rungs are the least needed to generate that permutation.
    5. Equivalently, to generate a permutation on n elements having c cycles, we would need a minimum of n - c rungs.  Do you see how that is equivalent to what we said in note d. above?  This will probably be on the test, so think about it.

  2. Permutations
    1. A permutation is an arrangement of some collection of distinct objects, relative to some "home" arrangement, which must be given or understood.
    2. There are n! = n x (n-1) x  ... x 2 x 1 different permutations of n distinct objects. 
    3. Permutations have parity; that is, every permutation is either odd or even. 
      1. The parity of a permutation is defined to be the number of inversions in the permutation.
      2. And inversion in a permutation is a pair of elements which is out of order relative to home position
    4. The parity of a permutation is equal to the parity of the number of rungs in any net diagram that generates that permutation
    5. And "even cycle" is a permutation that cyclically rearranges an even number of elements, and an "odd cycle" is a permutation that cyclically permutes an odd number of elements.
    6. Even cycles have odd parity, and odd cycles have even parity.
    7. A short rung in a net diagram is a rung that connects two adjacent vertical lines.
    8. The least number of short rungs needed to generate a given permutation is equal to the number of inversions in that permutation.  We also saw how to generate such a net diagram from the permutation:  Write the home position on top, the permutation below it, and connect like numbers with roughly straight lines.  Finally, replace each crossing point with a short rung, and "straighten out" the diagram.
    9. Permutations can be thought of as rearrangements of objects, where we move elements from their own home positions into the home positions of other elements.  For example, the permutation given by the net diagram to the right can be thought of as a permutation which leaves A and B in their own positions, but moves C to D's position, D to E's position and E to C's position.  Thus, this permutation is really just a 3-cycle on three of the elements.
    10. Permutations have cycle structure, referring to the cycles in the permutation.  Thus, the permutation shown in the net diagram above has the cycle structure (A)(B)(C, D, E), because A is left in its own position, B is left in its own position, but C moves to D's position, D moves to E's position and E moves to C's position.  The cycle structure (A, B, C)(D, E) would refer to a permutation that moves A to B's position, B to C's position, C to A's position, and swaps the positions of D and E.
    11. The composition of two permutations refers to first performing one permutation, then the other.  For example, let's compose the permutations (1, 2, 3)(4, 5) and (1, 5, 4, 2)(3). 
      1. We write (1, 2, 3)(4, 5) ° (1, 5, 4, 2)(3) to indicate that we do the permutation on the right first, then the one on the left.
      2. To find this composition, start a new cycle structure:  "(1, "
      3. Ask, where does "1" go?  In the right permutation, 1 goes to 5, and then in the left permutation, 5 goes to 4, so that in the composition, we say 1 goes to 4.  Our cycle structure now looks like "(1, 4, "
      4. Where does 4 go?  4 -> 2, then 2 -> 3, so 4->3 in the composition, and our cycle structure becomes "(1, 4, 3, "
      5. Where does 3 go?  3 -> 3, then 3 -> 1, so 3 -> 1 in the composition, which is the start of the cycle.  We therefore close off the cycle structure, giving "(1, 4, 3)" for our cycle structure so far.
      6. We don't yet know where 2 goes in the composition.  2 -> 1, then 1 -> 2, so 2 -> 2 in the composition, meaning that 2 is in a cycle all by itself.  Thus our cycle strcutre grows to "(1, 4, 3)(2)"
      7. Finally, where does 5 go?  5 -> 4, and 4 ->5, giving 5 -> 5 in the composition, so that 5 will be in a cycle by itself also.  So our final permutation is "(1, 4, 3)(2)(5)"
      8. We write this composition operation as follows:  (1, 2, 3)(4, 5) ° (1, 5, 4, 2)(3) = (1, 4, 3)(2)(5)
    12. As practice, verify that (1, 3)(2, 5, 4) ° (1, 3, 5, 2, 4) = (1)(2)(3, 4)(5).

    7
    		 15
    		 3
    		 6
    14
    		 2
    		 5
    		 11
    9
    		 1
    		 10
    		 8
    4
    		 12
    		 13
  3. Puzzles
    1. We talked about the fifteen puzzle and considered which starting positions could and which could not be solved. A starting permutation can be solved if and only if the permutation is even. 
    2. For example, the permutation in the puzzle shown to the right has an odd parity, so it could not be solved.
    3. How could you discover that this puzzle has odd parity?  Here are a few ways:
      1. Write down the permutation in a row, and count inversions:  7, 15, 3, 6, 14, 2, 5, 11, 9, 1, 10, 8, 4, 12, 13.  There are 49 inversions, so it's odd.
      2. Build the cycle structure and count cycles.  In this figure, 1 has moved to the position where 10 would have been, so 1 -> 10.  10 has moved to 11's position, and 11 has moved to 8's position, etc...  The cycle structure is (1, 10, 11, 8, 12, 14, 5, 7)(2, 6, 4, 13, 15)(3)(9).  There are 4 cycles, and, using item 1.e from above, we see that n - c = 15 - 4 = 11 is the least number of rungs with which this permutation could be generated.  Since 11 is odd, the permutation is odd.
      3. We could draw a net diagram for this permutation, any net diagram, and count rungs.  We'll find that there are an odd number of rungs, showing that the permutation is odd.
      4. We could make 15 pieces of paper with the numbers on them, put them in the position shown, and use swaps to (illegally) solve the puzzle.  It will require an odd number of swaps, showing that the permutation is odd.
      5. We could actually try to solve such a puzzle, and get down to the position where all the pieces are in place except for 14 and 15.  These will be one swap away from solved, and 1 is odd, and therefore unsolvable.
    4. On Rubik's Cube, it is impossible to solve a cube which has had one edge piece removed, flipped and replaced.  This is because each 90-degree face turn of the cube moves the edge stickers in two four-cycles.  Each 4-cycle is odd, and odd+odd is even.  This implies that the parity of the permutation of the edge stickers is always even, in any position that can be reached from a solved cube.  The permutation we get by removing, flipping and replacing a single edge piece is odd because it has one swap, and is therefore unsolvable.

  4. Counting  (Sections 1.1 - 1.3 in the text.)
    1. The sum rule:  If a set is partitioned into a collection of non-overlapping subsets, then the size of the set is equal to the sum of the sizes of the parts.
    2. The product rule:  If a task consists of k parts, and the parts can be completed in n1, n2, ..., nk ways respectively, then the total number of ways to complete the task is the product of the number of ways to complete its parts. 
    3. We can use a tree diagram to count things.  Always start a tree diagram with a "start" node, and then from each node, draw a branch showing each way to perform the next single part of the task you are considering.  The total number of ways to complete the task is equal to the number of nodes at the ends of the branches.  For example, the tree diagram to the right shows allf ways to toss a coin six times without getting a run of length 3.  It has 26 branches, so there are 26 such ways.
    4. There are k! = "k factorial" ways to arrange k distinct objects.  This is a consequence of the product rule given above. 
    5. When the objects are not distinct, we need a more general formula.  This brings us to our ANAGRAM formula for counting arrangements of objects which are not distinct.
      1. To count the number of arrangements of objects, some of which may be repeats, we initially imagine that all the objects are distinct by assigning different colors to the objects.
      2. Then we imagine grouping the arrangements together so that arrangements which are the same once color is removed end up in the same group.
      3. Each group will have the same number of arrangements in it, and this number will be the product of the k!'s, where k is the number of times a given letter is repeated.
      4. For example, the number of anagrams of AABBB would be 5! if the letters were all different colors, but then when we group them, we'll have inside each group 2!x3! arrangements:  2! for the A's arrangements, and 3! for the B's.  Thus, the total number of anagrams of AABBB would be 5!/2!3! = 10.
      5. The number of anagrams of MISSISSIPPI is 11!/4!4!2! = 34650.
    6. The quantity n Choose k refers to the number of ways to select k elements from a set of n distinct elements.  This quantity is equal to the number of anagrams of a word with n letters, k of them the letter "Y," and n-k of them the letter "N."  Thus, n Choose k = n! / k!(n - k)!.  For example, 10 Choose 2 = 45, and 5 Choose 5 = 1.  10 Choose 5 = 252, and n Choose n = 1 for all n.
    7. The number of ways to walk on a grid is also counted by anagrams.  In this case, if we are walking on a grid taking steps only in the South and East direction, and our destination is s blocks South of and e blocks East of our starting location, then there is a natural bijection between all ways to walk and the set of anagrams of a word with s S's and e E's.  For example, there would be 12! / 8!4! = 495 ways to walk from the top-left to the bottom-right in the figure to the right.

  5. Sets and Functions
    1. A set is some well-defined collection of elements, usually written inside curly braces with commas between the elements
      1. For example, the set of vowels is {a, e, i, o, u}
      2. The set of even numbers is {..., -4, -2, 0, 2, 4, 6, 8, 10, ..}
      3. The set of squares of integers less than 10 is {0, 1, 4, 9}.
    2. The size of a set X is the number of elements that set X has.  This is written |X|. 
    3. So if V is the set of vowels, then |V| = 5, and if E is the set of even integers, then |E| is infinite.
    4. A function is a correspondence between two sets, called the domain and range of the function, such that for every element of the domain, there is exactly one element of the range to which it corresponds.
    5. A function is thought of as being a function from the domain to the range.
    6. When we write the notation f : D -> R, then the set D is the domain of the function and the set R is the range.
    7. A function is called one-to-one (sometimes written "1-1") if for each element of the range there is at most one element of the domain which corresponds to it.
    8. A function is called onto if for every element of the range there is at least one element of the domain which corresponds to it.
    9. A function is called a bijection if it is both one-to-one and onto.
    10. If X and Y are sets, and there is some bijection between X and Y, then |X| = |Y|.  This is a useful fact for finding the size of some set.  For example, we used this fact to enable us to evaluate choose numbers (by finding a bijection with anagrams) and to count walks on a grid (again, by finding a bijection with anagrams).

      Topics Covered on Exam 2


  6. Functions and Cryptography

  7. Modular Arithmetic

  8. Fermat's Little Theorem

  9. The Euclidean Algorithm

  10. RSA