Department of Mathematical Sciences
Binghamton University

Math 386: Combinatorics Announcements
Fall 2011

Go to homework | course information | syllabus.

Index

Tests and Quizzes
Solutions and Extensions
Mathspeak
Additions and Corrections to Textbook
Chapter 1 2 3 4 5 6 7 8 14 17

Tests

Test I (Wed., Oct. 5 Changed to Mon., Oct. 10)

Covering all of Homework Sets I–V. Grading guidelines:

 	A       B       C       D       F
	82-100	61-81	40-60	34-39	0-33

Test II (Wed., Nov. 2)

Covering all of Chapters 5-7, including Homework Sets VI-VIII and part of V. Grading guidelines:

	A       B       C       D       F
	92-100	76-91	58-75	48-57	0-47

Test III (Tues., Dec. 6)

Covering Homework Sets IX-XII, i.e., Chapter 8, Sections 14.1 and 17.1-3 (but nothing about matrices), and Stirling's approximation.
Here is the test (PDF).
Grading guidelines:
A B C D F 62-100 46-62 30-45 24-29 0-23
If your grade on this test is below your grade on the other tests (including the final exam), I'll ignore it. If it's high, of course that's good.
I hope to have a smallish section of the final that will test the same topics as Test III so I can see how you can do when there's more time to think about it.
Final Exam (Wed., Dec. 14)

The final exam will cover the whole course, i.e., everything we've done. Regarding Section 17.4 you only have to know affine planes over Z_p as explained in class and in my notes. I won't ask about projective planes (too bad; they're lovely things). On Latin squares there will be no complicated questions, and nothing about orthogonal squares. There will be no questions about dual, derived, or residual designs, or about the matrix theory of designs.
The exam will be in room S2-145. The time is 2:00 p.m - 4:00 p.m. I will allow an extra 15 minutes. Grading guidelines:
```
	A       B       C       D       F
	113-150	83-112	54-82	45-53	0-44
```
Here are solutions for the final exam (PDF).

Solutions and Extensions

A list of extras I prepared (PDF documents).

A discussion of Stirling's approximation formula for n!, with applications to estimating binomial coefficients, Catalan numbers, and derangement numbers, and a comparison of the latter with the approximation D_n ≈ n!/e.

Solution of Chapter 4, Problem 4, on rooks in the staircase Ferrers diagram.

Solution of Chapter 6, Problems 32 and 36, on parity of a permutation.

[NEW] Solution of Chapter 14, Problem 23, on the submultiplicative property of pattern avoidance numbers.

[NEW] Explanation of Chapter 17, Section 4, on affine and projective planes and Latin squares.

[NEW] Solution of Chapter 17, Problem 40, on the size of a subdesign.

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 only one meaning in mathematics: "unique" = "only one". If you can't replace "unique" by "only one" in your writing, you're using it incorrectly.
"There is a unique" has one and only one meaning: "there is one and only one". If you can't replace "there is a unique" by "there is one and only one" in your writing, it's incorrect usage.
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 like a theorem, which is something that has to be proved.

A class is just a set. Sometimes it's handy to call a set whose elements are sets a "class" so as to keep things straight.

Additions and Corrections to Textbook

All uses of the word "quintessential" should read "essential".

Chapter 1

Ch. 1 begins with etymology, but it is a minor error (that doesn't affect the mathematics). Pigeonhole means a place to put things with similar properties when sorting. In the old days (before you were born, around 1850), mail was sorted by hand. (I remember it well?) A clerk stood in front of a big wooden structure partitioned into spaces, open in the front, labelled A, B, ..., Z. He held a pile of letters in his hand and put each piece into the box with the letter for the recipient's last name. The boxes were called "pigeonholes" and the process of sorting was called "pigeonholing". (The name came from actual holes for pigeons, originally; probably carrier pigeons.) Nowadays, "pigeonholing" something means classifying it too strictly; for instance if you pigeonhole Sam as a "genius", you're forgetting she has other characteristics as well (such as playing the oboe).

Chapter 2

The power set of a set S is the class of all subsets of S. I write it P(S). For the class of all k-subsets I write P_k(S).

An r-combination of a set is just an r-element subset.

A sequence or string is a list of objects in a definite order. The objects may or may not be different. If they are all different the sequence is an r-permutation.

An r-permutation of an n-element set S is a permutation of any r elements of S. A permutation of S is an n-permutation. A 0-permutation is an empty sequence (there is one of them, just as there's one empty set).

P(n,r) is defined as the number of r-permutations of an n-element set. If you write P(n,r) I will know that's what you mean. Theorem 3.2 gives a formula for P(n,n). Theorem 3.13 gives a formula for P(n,r).

C(n,r) is defined as the number of r-combinations (r-element subsets) of an n-element set. If you write C(n,r) I will know that's what you mean. The book uses the binomial coefficient to mean this, but it's better (IMHO) to use the binomial coefficient to stand for the formula. We prove the formula for C(n,r) in Theorem 3.16.

Chapter 3

Stirling's Formula, Eq. (3.1) (also called Stirling's Approximation to n!), is often a good way to estimate how big is a number that involves binomial coefficients. See the linked writeup (PDF), which also treats the derangement numbers (Ch. 7).
Ch. 3, Exercise 24: Just for the record, the definition of a magic square is not the right one. It's the one used by some mathematicians but not by people interested in magic squares. The "correct" definition includes at least the following conditions: (1) The rows, columns and both diagonals all have the same sum (the magic sum). (2) All the numbers are different from each other. (3) No negative numbers. (4) Most definitions also say the numbers should be 1 to n², but that isn't universal.

Ch. 3, Exercise 33: In case you weren't sure, "precede" doesn't mean "immediately precede".

Chapter 4

Section 4.3 on the binomial theorem is missing an important special case, namely,
(1−x)^-r = ∑_n=0^∞ binom(n+r−1, n) xⁿ
when r is a positive integer. For the proof, just apply the general binomial theorem and simplify as much as possible.

Ch. 4, Exercise 20: "log-concave" is short for "logarithmically concave". It means the sequence of logarithms is concave. (Never mind that definition; we don't use it.)

Ch. 4, Exercise 54(a): "we can always select at most".

Chapters 3, 4, 5

Chapters 3 and 4 tend to treat problems of choice, where you pick one or more objects (and possibly arrange them in order). Chapter 5 treats distribution problems, where you give out objects. Some choice and distribution problems are equivalent (in disguise), but some are not.

Chapter 5

The book (Section 5.1) talks about weak compositions of an integer n into k parts. That means a k-tuple (ordered!) (x₁,..., x_k) of integers ≥ 0, such that x₁ + ... + x_k = n. A composition of n into k parts is the same, but with integers > 0. A Diophantine sum or weak composition of n is any equation of the form x₁ + ... + x_k = n where x₁, ..., x_k are integers, not necessarily ≥ 0 (they might be restricted in other ways).

Section 5.3 is about partitions of an integer. Sections 5.1 and 5.2 are about compositions of an integer and partitions of a set. There are also compositions of a set. Here is a table (similar to what's in the book but for partitions and similar problems):

Set Partitions {B₁, B₂, ..., B_k} No B_i empty. n-set partitioned into k parts: # = S(n,k).		Set Compositions (ordered set partitions) (B₁, B₂, ..., B_k) No B_i empty. n-set composed into k parts: # = k! S(n,k).
Integer Partitions {a₁, a₂, ..., a_k} with a₁ ≥ a₂ ≥ ... ≥ a_k and all a_i > 0. # of partitions of n: p(n). # of partitions of n into k parts: p_k(n).		Integer Compositions (a₁, a₂, ..., a_k) with all a_i > 0. # of compositions of n: 2^n-1. # of compositions of n into k parts: (n-1 choose k-1).
Weak Set Partitions {B₁, B₂, ..., B_k} B_i may be empty. # of weak partitions into k parts: S(n,0)+S(n,1)+...+S(n,k).		Weak Set Compositions (B₁, B₂, ..., B_k) B_i may be empty. # of weak compositions into k parts: more complicated.
Weak Integer Partitions {a₁, a₂, ..., a_k} with a₁ ≥ a₂ ≥ ... ≥ a_k and all a_i ≥ 0. # of weak partitions of n into k parts: p₁(n)+p₂(n)+...+p_k(n).		Weak Integer Compositions (a₁, a₂, ..., a_k) with all a_i ≥ 0. # of weak compositions of n into k parts: (n+k-1 choose k-1).

See the linked PDF file for a solution of Chapter 5, Problem 4.

Problem 9 of Ch. 5 is wrong. In fact, p_1,0(r) = 1 (a polynomial), p_2,0(r) = r (a polynomial), p_2,1(r) = r (a polynomial), but p_3,0(r) = r + [r/2], where [x] := the greatest integer in x, not a polynomial.

Chapter 6

The notation for permutations can be confusing. I explain it this way. A permutation p of [n] can be written in two ways.
The one-line notation (or sequence notation) is
p = (p₁, p₂, p₃, ..., p_n) or, as the book prefers, p₁p₂p₃...p_n.
This means that, as a function, p(1) = p₁, p(2) = p₂, and so on. We also think of it as meaning the members of [n] are lined up in a row, with p₁ first, then p₂, etc.
The cycle notation looks like this:
p = (a₁a₂...a_k)(b₁b₂...b_l)...(c₁c₂...c_m).
It means that, as a function, p(a₁) = a₂, p(a₂) = a₃, ..., p(a_k) = a₁, p(b₁) = b₂, etc.
There are two ways to transform cycle notation into one-line notation. The first way keeps the same permutation. It converts the cycle notation above into the one-line notation with p(a₁) in position number a₁, p(a₂) in position number a₂, etc. The second way transforms p into a different permutation,
q = a₁a₂...a_k b₁b₂...b_l ... c₁c₂...c_m,
where we assume the cycle version of p was written in canonical form (each cycle has the maximum element at the beginning, and these maximum elements increase from cycle to cycle as we go left to right). This gives a function (called g in the book) S_n → S_n. That is, g is defined by g(p) = q.
Thus, we have two ways to convert cycle notation into one-line notation. The first one keeps the same permutation (so it is the identity function on S_n), but it changes the sequence (the order of the numbers). The second changes the permutation (it is the function g) but keeps the sequence. Don't mix these up! It does get tricky, though.

For those who want a more formal explanation, here is my way to do so. Define two sets:
Perm(n) = {sequences of length n with entries from [n], without repetition}
= the set of permutations as sequences,
and
S_n = {bijections from [n] to [n]}
= the set of permutations as bijections.
Now I define two functions h, g: S_n → Perm(n). They are defined by their effect on a permutation in cycle form,
p = (a₁a₂...a_k)(b₁b₂...b_l)...(c₁c₂...c_m).
The first function, h, is defined by
h(p) := (p₁, p₂, p₃, ..., p_n)
where p_i = the successor element to i in the cycle that contains i. The second function, g, is defined by
g(p) := a₁a₂...a_k b₁b₂...b_l ... c₁c₂...c_m.
Thus, the q above is g(p) and the "p in sequence form" above is h(p).

In the book, the author identifies p (cycle form) with h(p) (sequence form) without mentioning the function h, as they represent the same permutation if a sequence is interpreted as one-line notation. Thus, a sequence or string e₁e₂...e_n "is" the cycle-form permutation h⁻¹(e₁e₂...e_n). It can get confusing when he jumps back and forth between sequence and cycle form since he never mentions h, but he's careful to mention g (or at least to remind you he means to use g).

On page 120, the text labelled "Solution" is really the Proof of Lemma 6.15.

On page 122, in the middle, the text "create a singleton cycle with this value" should read "create a singleton cycle with the last value in c_h".

In Problem 25 of Ch. 6, "n-permutations" should be "m-permutations".

In Problem 27 of Ch. 6, "six" should be "[6]".

In Problem 32 of Ch. 6, we "call a permutation even (resp. odd) if it has an even (resp. odd) number of inversions."

For a solution to Problems 32 and 36 of Ch. 6, see the linked PDF file on parity of a permutation.

Chapter 7

Ch. 7 is about the Principle of Inclusion and Exclusion (P.I.E.), also called the Inclusion-Exclusion Principle (P.I.E.), and which this book calls the sieve formula (P.I.E.).

We can estimate the derangement numbers D_n in a couple of ways. Stirling's Formula, Eq. (3.1), gives one way. Another way, that is really remarkable, is that D_n is the nearest integer to n!/e. See the linked writeup "Stirling's Approximation and Derangement Numbers" (PDF) for a proof using the power series for e^x.
Chapter 8
In the middle of page 152, the solutions should be A = −100/3 and B = 100/3.

In Theorem 8.5, the last line of page 156, n should be [n].

On page 163, "at most n&minus1 summands" should say "at most n summands".

At the top of page 165, "first (respectively, second) member" should read "first (respectively, second) term".
In the next line, interchange α and β so it reads "by β (respectively, α)".

In Theorem 8.15, line 5, "build a structure of the given" should be "build a structure of the first".

On page 167 just above Example 8.19, "this second term summand the term" should read "this second term has summand".

In Theorem 8.15 I do not see a need for the assumption that b₀ = 1.

In Problem 8.50, line 4, "descent" should be "ascent".
The answer is: (a) OGF = e^−x/(1-x). (b) Hint: The OGF for the derangement numbers D_n is e^−x/(1-x). Thus:
Proposition. The number of permutations p of [n] with the first ascent in an even position (counting p_n as an ascent) equals D_n.

I found this surprising, and it suggests a follow-up question:
- Find a bijection f: Perm_n → Perm_n such that
  1. f({derangements}) = set of permutations with first ascent in an even position, and more generally,
  2. for each X ⊆ [n], f({permutations with fixed set X}) = set of permutations with first ascent in an odd position and some other property of ascents, the exact property depending on the set X.
The idea is that there should be a general pattern to the correspondence between fixed sets and ascents.

In the solution to Problem 8.4, the equation 1 = (A−B)x + αB + βA should read 1 = (A+B)x + αB + βA.

In the solution to Problem 8.16 (Motzkin numbers), there is a quicker way to get the recurrence relation: use Theorem 8.13. I'll show it in class.

Chapter 14

In Problem 14.8, you partition the polygon into any number of triangles and one quadrilateral. Question: How many triangles will you have?

The definition of L for Problem 25 is stated in Problem 24.

The solution to Problem 14.7 has an error. The correct value is d₀ = 1 (not d₂ = 0). We deduced why in class, where I showed a different way to get the same recurrence relation as the book has. (The book's solution is perhaps more complicated than the one I presented.)
I said to pick one side of the (n+1)-gon and call it the "base". Number the vertices of the polygon 0, 1, 2, ..., n+1 so the base is the edge 0-(n+1). The base must be an edge of a triangle in the dissection into triangles, and the third vertex of the triangle is at vertex k where 1 ≤ k ≤ n. This cuts the polygon into two smaller polygons. Compute the side lengths of the smaller polygons so you can find the number of ways to dissect each of them into triangles. Then summing over k gives d_n, as in the book. Continue as in the book: you recognize the generating function as the Catalan g.f., so d_n = C_n, the Catalan number. (Check n = 1, 2, 3, to be safe.)

Chapter 17

The book calls the elements of the basic set S of a block design "vertices". I never heard anyone else do this, and I won't. I will call them points, which is a common name. An older name is "varieties".

In class I gave a modification of the book's Proposition 17.17, which I called:
Proposition 17.17'. The dual of a symmetric design is another symmetric design, and it has the same parameters.
This is the real main result; the book's 17.17 is a lemma to prove it. Do you see how 17.17 implies 17.17'?

Section 17.4 needs a major rewrite; it does not explain enough. See my write-up on affine and projective planes and Latin squares and the notes from Wednesday's class (12/7). Here's a brief summary.
I explained the construction of an affine plane of order p (a prime number) using modular arithmetic with modulus p. That is, we use the set Z_p = {0, 1, 2, ..., p−1} and take the point set of the affine plane to be Z_p × Z_p, with lines given by linear equations, y = mx+b and x = a.
Then I explained how we add "points at infinity", one for each parallel class of lines, so that parallel lines really do meet at infinity (as we used to say jokingly in high school). Also, these points at infinity form one new line, the "line at infinity". That's how to construct the projective plane with coordinates in Z_p.
Note: What I mean by "coordinates in Z_p" is that we can label the points by ordered pairs in Z_p × Z_p and define the lines by linear equations. That's the explanation for the affine plane. The explanation of "coordinates" for the projective plane is a bit more complicated so I'll skip it, but it would explain Bona's cryptic remarks about triples (x,y,z) in a finite field and identifying triples that "are constant [scalar] multiples of each other." (He means that we're doing vector spaces of dimension 3 over a finite field. A "finite field" is a generalization of Z_p. I could explain all this if we had time enough, but we don't, and for the final exam you only have to know affine planes over Z_p.)

In Section 17.4.1, whenever he says "derived design (of a projective plane)" he means "residual design (of a projective plane)".

The name Fano plane comes from the fact that it was first investigated by Gino Fano (a bit over 100 years ago).

Page 426, line 7 up should read "of a projective plane of order four."

In Problem 17.25 we need a definition of a balanced design that is not necessarily a BIBD.
Definition. A block design is balanced if every pair of points belongs to the same number of blocks. (This number is denoted λ.)
Explanation: This problem proves an important fact about block designs: that in defining a (v, k, λ)-design, you don't need to specify that r exists; it's a theorem.

In Problem 17.30, S must be a finite set. Otherwise the problem would be false.

In Problem 17.40, "the set of blocks of F is a subset of the set of blocks of D."

Go to homework | course information | syllabus.