Math 386: Combinatorics Announcements

Go to homework | course information | syllabus.

Tests

Test I (Sept. 28)

Covering Sections 1.1-1.3 and all of Chapter 3 (that is, HW Sets I-IV), except that you should skip the first part of 1.2 (cutting up the cube). Grading guidelines:

 	A       B       C       D       F
	81-100	64-80	45-63	38-44	0-43

Test II (Oct. 26)

Covering Chapter 5 (omitting 5.7 and the multinomial theorem) (that's HW Sets V-VIII). Grading guidelines:

	A       B       C       D       F
	76-100	56-75	35-55	28-34	0-27

Test III (Nov. 30)

Covering Homework Sets IX-XIII, i.e., Sections 6.1-5 (omit the proof of the Principle of Inclusion and Exclusion), 2.1-2 (except Application 6), 10.1 to page 373, and 10.4 to the middle of page 403 (except page 400 and the top of page 401). Grading guidelines:

	A       B       C       D	F
	90-115	74-89	58-73	51-58	0-50

Final Exam (Mon., Dec. 11)
The final exam will cover the whole course, i.e., everything we've done, with the exception of (1) the first part of Section 1.2 (cutting up the cube), (2) the proof of the Principle of Inclusion and Exclusion, (3) affine planes. It will emphasize Latin squares, but that will be less than half the exam.
The exam will be in room AA-G007. The time is 11:00 a.m. - 1:00 p.m. I will allow an extra 15 minutes. Grading guidelines:
```
	A       B       C       D       F
	110-150	85-109	63-84	54-62	0-53
```

Mathspeak

Here are some tips on using English correctly and clearly in mathematics.

To write "a divides b" or "a is a factor of b" as a formula, use a vertical bar: a|b .

``Unique'' has one and only one meaning in mathematics: ``unique'' = ``one and only one''. If you can't replace ``unique'' by ``one and only one'' in your writing, you're using it incorrectly.
(N.B. In correct standard English, ``unique'' means ``of which there is only one'' or a closely related meaning -- see Oxford English Dictionary. It does not mean ``different''; if you mean that, say ``different'' or, in mathematics, ``distinct''.)

``Distinct'' means ``different from each other''.

A definition is what tells you the meaning of a word or phrase. In math, you should be able to replace the word by its definition. If you can't, you are probably using it incorrectly. A definition is not in any way like a theorem, which is something that has to be proved.

Corrections and Additions to Textbook

Here is a summary sheet (click!) of basic counting problems and formulas.
Ch. 2, #16. It should also be assumed that acquaintanceship is symmetrical: i.e., if A is acquainted with B, then B is acquainted with A. (This isn't always so in real life!)
In Section 6.3, p. 174, line 15, the expression (n-2)!D should be just (n-2)!.
Exercise 32 has two errors. First, the board is backwards: the correct board is the X'd squares. Second, the formula should be a(n,k) = 2n/(2n-k)·(2n-k choose k) for the number of ways to place k rooks in the X'd squares.
However, there is another interpretation that makes even better sense to me. Suppose we want to place n nonattacking rooks in the open squares (without X's). Then we need to know the r_k's. They are exactly the a(n,k)'s defined above. So, they are the information we need to count rook placements in the open squares.
Don't forget that Exercise 32 has two parts. One part is to show that a(n,k) has the formula given (I mean the correct one). The other part is to show that a(n,k) counts the number of ways to choose k children, as specified in the exercise. I'm not sure which part should be done first, but I incline towards doing the second part first and using it to find the formula.
In the answers to Ch. 6, the last 3 problem numbers are 1 greater than they should be.
In Ch. 10, page 341, the term ``GCD'' is introduced. It is an abbreviation for ``greatest common divisor,'' as mentioned in Theorem 10.1.2 on p. 343.
In Ch. 10, page 343, in the table at the top, the entries in Cols. A and B are sometimes interchanged from what the algorithm would give.