Friday Nov 17 and Mon Nov 20

Inversions of a permutation = number of pairs (i < j) such that pi(i) > pi(j).
Neighborly transpositions = (i i+1), in cycle notation.
Theorem: pi can be written as a product of invs(pi) many neighborly transpositions.
Theorem: if pi is written as a product of k neighborly transpositions, then k is greater than or equal to invs(pi), and k is congruent to invs(pi) mod 2.
Definition. An even permutation is one with invs(pi) even, similar def for odd permutations.
Theorem: invs(pi) + invs(rho) is congruent to invs(pi o rho) mod 2.
Theorem: invs(any transposition) is odd.
Theorem: if pi is written as a product of k transpositions, then k is congruent to invs(pi) mod 2.
Theorem: the Sam Loyd 14-15 puzzle is insoluble.

Last HW, due Wednesday Nov 29

1. Let w0 denote the permutation of {1..n} with the most inversions. Show that w0 o w0 = identity.

2. For any pi, show that invs(pi) + invs(w0 o pi) = invs(w0). Also show invs(w0 o pi) = invs(pi o w0).

[More coming in a couple of days]

Wednesday Nov 15

Midterm review.
Chinese Remainder Theorem.
Permutations: one-line notation and cycle notation.

HW due Monday (short)

1. Let pi be a permutation of {1..n}. When written out in cycle notation (including each i s.t. pi(i)=i as a cycle of length 1), let k be the number of cycles.

Let (i j) be the permutation that switches i and j, and leaves the other elements alone. (So this permutation has n-1 cycles, according to the definition above.)

Show that the product pi * (i j) has either k-1 or k+1 cycles, and explain when it's k-1 and when it's k+1.

5.3 #34,35,38

Midterm results

The midterm, with answers, is here.

Grade histogram:

100-80	A	******
80-60	B	****
60-40	C	******
40-20	D	**
20-0	F

Answers to the real midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the actual midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the actual midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the practice midterm

1. Say that p is prime, and p | a. Show that for some integer m,
p² | ma.


Let m=p. Then p | a
=> a = pb for some b
=> ma = mpb = p²b for some b
=> ma is a multiple of p²
=> p² | ma.


2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.


It is impossible to make a function from X to Y, since the elements in X have nowhere to go. So indeed, every function from X to Y is raining frogs1:1.


3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mⁿ.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.


To specify a function from X to S, we need to say where each element of X goes. We already know where the m elements of S go: to themselves. It remains to specify where the other n-m elements of X go, in S. Each has m independent possibilities, giving m^n-m, just as when we counted all functions X->S.


4. Let X be a set. How big can X be, if

every relation is symmetric?

every relation is transitive?

every relation is reflexive?

Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.


Sym: 1. The relation {(a,b)} on {a,b} is not symmetric.
Trans: 1. The relation {(a,b),(b,a)} is not transitive.
Ref: 0. The relation {} on {a} is not reflexive.


5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).


For p o f to not be onto, either everything in X goes to even, or to odd.
If X all goes to odd, then f:X->Y has to take everything to 1. One function so far.
If X all goes to even, then f:X->Y is really a function to {0,2}, and there are 2³ such functions. Eight more.

Forgive me for not drawing these in ASCII.


6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)³ is congruent to a³+b³ mod 3.


(a+b)³ = a³ + 3a²b + 3ab² + b³.
So the difference between that and a³ + b³ is 3(a²b + ab²), a multiple of 3.


7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.

No; let a,b=1. Then (a+b)⁴ is 0 mod 4, but a⁴+b⁴ is 2 mod 4.
(In fact it holds for all prime exponents.)

Some practice midterm questions

If having thought about a question you decide you're really stuck, leave a comment asking for a hint. Conversely, if you have a hint to suggest, leave that comment!

1. Say that p is prime, and p | a. Show that for some integer m,
p² | ma.

2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.

Yes, really. This question is written correctly, and means exactly what it says.

3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mⁿ.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.

(I'll leave the actual number in the comments, but then you still should think about proving it.)

4. Let X be a set. How big can X be, if

every relation is symmetric?

every relation is transitive?

every relation is reflexive?

Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.

5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).

6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)³ is congruent to a³+b³ mod 3.

7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.

Office hour today 3-4 / Midterm topics

Usually it's 4-5 (after class), but there being no class I'm moving
it up an hour.

This midterm will be run the same as the last one. Focus on number theory, equivalence relations, and 1:1/onto properties of functions.

Wednesday Nov 1

Properties of functions: injective AKA 1:1, surjective AKA onto, bijective.
Functions have inverses iff they're 1:1 and onto.
If f,g are injective, so is g o f.
If g o f is injective, so is f (maybe not g).

Statement: every function X -> Y can be factored as a surjection X -> X/~, then a bijection X/~ -> S, then the inclusion of a subset S -> Y.
We'll prove it next time.

Monday Oct 30

Equivalence relations vs. "partitions" of a set.
From a partition, we built an equivalence relation, and vice versa.
(There's lots to check about these recipes, and it took the whole hour, without even getting to prove that each recipe was the other's inverse.)