Friday, January 18, 2008 Notes Math/CSCI 2427
by David Sichi

1-8 was put up on the board

Definition:  permutation - some arrangement of a set of objects, relative to some fixed home arrangement or order. (IE anything mixed up)

3142 - permutation of 1234
1234 would be the home order
marAschino - permutation of the word hArmonicas
"hArmonicas" is the home position.  Note that one of the letters "A" was capitalized, so that it would be different from the other "a" in the word.  In general, we will be permuting sets of distinct objects.

The big point from Wednesday's class was that all permutations have parity.

We mixed the numbers 1-8 on the board to demonstrate parity.
15324768 has odd parity, which Kevin knew because he watched them be swapped, and it took three swaps.
Check parity by counting the number of inversions, which is the number of times an object comes before an object that normally comes AFTER it in home position.
Trying to get back to 15324768, did so in 15 swaps, which still has odd parity.
Proving that you can't get to the 15324768 with an even number of permutations.
Went from 12345678 to 12375648 which is 1 swap, but 5 inversions, so it still has odd parity.
Then went from 12345678 to 17345628 which is 1 swap, but has 9 inversions.
Suppose there are B numbers between the pair that was swapped, then we will get B + B + 1 pairs that are swapped.
number of inversions is 2B + 1

Theorem:  Any transposition (swap) inverts an odd number of pairs.
Corollary:  Each time we swap a pair of objects in some permutation, we change the parity of that permutation.
The home permutation is always even.
This was proven by a lengthy amount of transpositions where the class was told to speak out loud whether it was even or odd after every swap. After a minute or two of swapping, we arrived at home position in an even number of swaps, as expected, verifying that the parity was still even

Theorem:  If we start at home position, do some transpositions, and end at home position, the number of transpositions we did must have been even.
Permutations also have cycle structure.  More will be discussed on Friday, 1/25, about cycles.

A horizontal connecting line in a net diagram is a transposition.

EC +10 find parity of cycles of ALL sizes.