Department of Mathematical Sciences
Binghamton University

Math 386: Combinatorics
Announcements
Fall 2012

Index

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

Tests

• Test I (Tues., Oct. 16)

  Covering Homework Sets I–VI, that is, Chapters 3–5 and Theorem 2.4. Grading guidelines:

   	A       B       C       D       F
  	81-100	61-80	41-60	33-40	0-32
  

• Test II (Tues., Nov. 20)

  Covering Homework Sets VII–XI. There will be no Catalan numbers (Sect. 8.1.2.1), no general compositional formula (Theorem 8.15), and no exponential generating functions (Sect. 8.2). Grading guidelines:

  	A       B       C       D       F
  	87-100	71-86	55-70	50-54	0-49
  

  Here are solutions for Test II (PDF).

• Final Exam (Wed., Dec. 19)

  The exam will be in room S2-144. The official time is 2:00 p.m - 4:00 p.m. I will allow an extra 15 minutes.

  The final exam will cover the whole course, i.e., everything we've done (with the exceptions below). It will give extra emphasis to anything we cover after the last class test; that is, HW sets XII–XIV.

  Notes about what will be on the final exam:

  • Generating functions: No general compositional formulas (Theorems 8.15 and 8.27).
  • Affine and projective planes (Section 17.4 and my notes): Only over prime fields, that is, Z_p (p prime), also known as F_p.
  • Latin squares (Section 17.5 and my notes): No complicated questions. There could be basic questions on orthogonality.
  • Error-correcting codes (Section 17.5): I will only ask about binary codes, and nothing on linear codes.
  
  Grading guidelines:

  	A       B       C       D       F
  	105-150	85-104	60-84	52-59	0-51
  

  Here are solutions for the final exam (PDF).

Quizzes

Note on quizzes: The quiz points are similar to homework points, not test points. A quiz point is a rather small fraction of a test point. The purpose of quizzes is learning, which is why I want to discuss the answers immediately.

• Quiz 1


• Quiz 2 (10/31)
  1. What is the difference between "equivalent" and "equal"?
         Two objects are equal if they are the same object (they might be described in different ways). Two objects are equivalent if there is an equivalence relation in which they are related.
         Two mathematical expressions are equal if they have the same value. Two expressions are equivalent if there is an equivalence relation on their values such that the values are equivalent.
         (Either of these is a good answer, but I think the first one is more basic, at least for combinatorics.)
  2. When should you not say something is true "by definition"?
         When it is true for a different reason, such as by being proved. (Or, of course, when it is not true; but that was not the purpose of the question.)

Solutions and Extensions

A list of extras I've 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.


• Explanation of Chapter 17, Section 4, on affine and projective planes and Latin squares.

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

  Chapter 2 3 4 5 6 7 8 17

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



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

• Combination and permutation numbers (also see notes on Chapter 2): We define
  • C(n, r) = the number of r-combinations (i.e., r-element subsets) of an n-element set,
  • P(n, r) = the number of r-permutations of an n-element set.
  We prove formulas for P(n, r) in Theorem 3.13 and for C(n, r) in Theorem 3.16.


• A rook is a chess piece that moves any distance horizontally or vertically. Thus, if two rooks occupy the same row or column, they are attacking each other.


• Proposition 3.10 is the most useful third of a bigger theorem, which is basic in many counting questions.
  Theorem 3.10'. Let X and Y be sets and f: X → Y a function.
  1. If f is a bijection, then |X| = |Y|.
  2. If f is an injection, then |X| ≤ |Y|.
  3. If f is a surjection, then |X| ≥ |Y|.


• A round-robin tournament is a competition in which there are 2n players (an even number), and 2n−1 rounds of play. In each round, all the competitors are paired up, in such a way that over all the rounds of play, every player is paired with every other player. (The players that are paired up in each round play once, and their scores are recorded.)


• 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 15: The question means: In how many ways can she choose the lab days?
      There is a little mistake in the solution. Can you find it?


• 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 16: S(n, k) should be s(n, k).


• 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 30: The problem is false as stated. The proper requirements are that n, k ≥ 2. (What happens if n or k = 1?)


• Ch. 4, Exercise 54(a): There is an extra word "neither" in the statement. The problem should read: "without selecting two subsets so that one of them contains the other." Then (a) asks for "at least (n choose m) subsets, where m = n/2 if n is even and m = (n−1)/2 if n is odd."



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 {B1, B2, ..., Bk} No Bi empty. n-set partitioned into k parts: # = S(n, k).		Set Compositions (ordered set partitions) (B1, B2, ..., Bk) No Bi empty. n-set composed into k parts: # = k! S(n, k).
  Integer Partitions {a1, a2, ..., ak} with a1 ≥ a2 ≥ ... ≥ ak and all ai > 0. # of partitions of n: p(n). # of partitions of n into k parts: pk(n).		Integer Compositions (a1, a2, ..., ak) with all ai > 0. # of compositions of n: 2n-1. # of compositions of n into k parts: (n-1 choose k-1).
  Weak Set Partitions {B1, B2, ..., Bk} Bi may be empty. # of weak partitions into k parts: S(n,0)+S(n,1)+...+S(n,k).		Weak Set Compositions (B1, B2, ..., Bk) Bi may be empty. # of weak compositions into k parts: more complicated.
  Weak Integer Partitions {a1, a2, ..., ak} with a1 ≥ a2 ≥ ... ≥ ak and all ai ≥ 0. # of weak partitions of n into k parts: p1(n)+p2(n)+...+pk(n).		Weak Integer Compositions (a1, a2, ..., ak) with all ai ≥ 0. # of weak compositions of n into k parts: (n+k-1 choose k-1).



• See the linked PDF file for a solution of Exercise 5.4.


• Exercise 5.16 has a mistake.



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).


• There is a close relationship between permutations of [n], set partitions of [n], and integer partitions of n, which is shown in the table:
  
  

  Permutation p	(a1...ak)(b1...bl)...(c1...cm)	Cycle form
  Set partition π	{ {a1,...,ak}, {b1,...,bl}, ..., {c1,...,cm} }	Partition whose blocks are the sets corresponding to the cycles of p
  Integer partition	n = k + l + ... + m	Type of p (and of π), that is, the sizes of the cycles (and of the blocks)

  
  There are many permutations with the same type. (Another way to say the same thing: Many permutations correspond to the same partition of n.) Similarly, there are many partitions of [n] with the same type. This table shows the numbers. For each i = 1,2,..., the number m_i is the number of parts of λ that are equal to i.
  
  

  Permutations of [n]	n! / n1 n2 ... nr m1! m2! m3! ...	Theorem 6.9
  Partitions of [n]	n! / n1! n2! ... nr! m1! m2! m3! ...	Theorem 5.22
  Partition λ of n:   n = n1 + n2 + ... + nr	1



• "n-permutation" is short way of saying a permutation of [n].


• In the proof of Lemma 6.4, the last lines should read "repeating this step j−2 more times, we get x = p^k−j(x), where k−j > 0. Then we let i = k − j.


• In the proof of Lemma 6.13, there should be the definition G₀(x) = 1.


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


• In the proof of Lemma 6.18, near the end of the first paragraph, "that cycle of q" should be "that cycle of p".


• 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".


• At the top of page 123, "Solution" should be "Proof".


• In Exercise 6.25, "n-permutations" should be "m-permutations".


• In Exercise 6.27, "six" should be "[6]".


• In Exercise 6.32, we "call a permutation even (resp. odd) if it has an even (resp. odd) number of inversions."


• The book's notation for the identity permutation (Exercises 6.38 and 6.39) can be confusing. 1 (sometimes) means the identity permutation – also written (1)(2)...(n) and 12...n – but (usually) it means the symbol 1 that is permuted.


• For a solution to Exercises 6.32 and 6.36, 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].


• There should be a corollary to Theorem 8.5 that tells you what to do when k is a fixed number, [n] is split into k intervals (possibly empty), S₁, ..., S_k, and a structure of type i is built on interval S_i, for each i = 1, ..., k. The ordinary generating function for the number c_n of ways to do this is
      C(x) = A₁(x)A₂(x)...A_k(x).
  Theorem 8.5 is the case k = 2. The corollary can be proved by induction on k.


• On page 161, line 4 up, 0 < k < i should read 0 < k < 2i.


• At the top of page 163, the first few Catalan numbers are c₀=1, c₁=2, c₂=5, etc. 0 is not a Catalan number.


• On page 163, "at most n−1 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.19, find an explicit formula for R(x), not r(n). R(x) is the ordinary generating function of r(n). An explicit formula for r(n) is difficult.


• There should be a corollary to Theorem 8.21 that tells you what to do when k is a fixed number, [n] is split into k subsets (possibly empty), S₁, ..., S_k, and a structure of type i is built on subset S_i, for each i = 1, ..., k. The exponential generating function for the number c_n of ways to do this is
      C(x) = A₁(x)A₂(x)...A_k(x).
  Theorem 8.21 is the case k = 2.


• In Problem 8.35, H_n should be h_n.
      Also, you can easily find the exact solution for h_n in this problem (unlike in Problem 8.34, for example).


• 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 Exercise 8.4, the equation 1 = (A−B)x + αB + βA should read 1 = (A+B)x + αB + βA.


• In the solution to Exercise 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 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".


• Two block designs, D = (S, B) and D' = (S', B'), are isomorphic if there is a bijection f: S → S' such that the blocks of D' are precisely the sets f(B) where B is a block of D. That is, B ∈ B if and only if f(B) ∈ B'. The function f is an isomorphism from D to D'.
      An automorphism of D is an isomorphism of D with itself.


• In class I give a modification of the book's Proposition 17.17, which I call:
      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'?


• Proof of Theorem 17.18, line 2: "Proposition 17.15" should be "Corollary 17.16".


• In Definition 17.21, the point set of the residual design is the set S − B.


• In Definition 17.22, the point set of the derived design is the set B.


• Section 17.4 needs a major rewrite; it does not explain enough. See my write-up on affine and projective planes and Latin squares.


• 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 Section 17.5, the terminology code over Bⁿ means a code over B of length n.


• Here are two important properties of binary words, not necessarily in a code. The book mentions them rather too quickly.
      Lemma 1. If x, y are two words in Bⁿ, the distance d(x,y) = wt(x+y).
      Corollary. If x is a word in Bⁿ and 0 is the zero word, then wt(x) = d(x,0).


• Here is a simpler definition of a linear code, equivalent to that on page 434.
      Definition. A binary linear code is a code over B such that the sum of any two codewords is also a codeword. (That includes when the two codewords are the same.)
      (Being a "subspace" of Bⁿ just means that if you have two words in your set, their sum is also in the set).
      Here is an important fact about binary linear codes, which the book doesn't emphasize.
      Lemma 2. The 0 word belongs to every binary linear code.


• In Problem 17.10, change "each block is a proper subset of the set of vertices" to "each point is in more than one block".
      Also, the solution on page 441 is wrong.


• In Problem 17.16, you need the definition of isomorphism given above.


• The solution of Problem 17.21 is wrong. The statement that after rearranging columns the squares remain orthogonal is false. (It is not believable without proof, even if it were true.) The correct proof does not permute the columns of each square; it permutes the symbols. That operation does preserve orthogonality.
      Also, in the last two lines of the proof, (i,i) and (1,i) should be (b,b) and (1,b), respectively.


• The beginning of the solution of Problem 17.22 should state that in Example 17.1, q = 4.


• 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."

  Chapter 2 3 4 5 6 7 8 17