Department of Mathematical Sciences
Binghamton University

Math 386: Combinatorics Announcements

Index

• Tests and Quizzes
• Mathspeak
• Additions to Textbook
• Corrections to Textbook
• Term Project Possibilities

Tests

• Test I (Tues., Sept. 29)

  Covering all of Homework Sets I-IV. Grading guidelines:

   	A       B       C       D       F
  	84-100	71-84	56-70	50-55	0-49
  

• Test II (Tues., Oct. 27)

  Covering Chapter 5 (omitting 5.6) and Sections 6.1-3 (that's HW Sets V-VII). Grading guidelines:

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

• Test III (Tues., Dec. 8)

  Covering Homework Sets IX-XII, i.e., Sections 3.1-2 and Chapter 7 (except 7.3). -Grading guidelines:

  	A       B       C       D	F
  	90-100+	80-89	70-79	65-69	0-64
  

• Final Exam (Mon., Dec. 14)

  The final exam will cover the whole course, i.e., everything we've done.

• Quiz 1 (9/8/09).
• Quiz 2 (9/22/09): no solutions or with solutions.

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.

Additions to Textbook

• Here is a summary sheet (PDF) (or in PostScript) of basic counting problems and formulas.


• And here is an informative note (PDF) on magic squares of all orders, odd or even. (Just 5 pages.)


• This is a well illustrated article about the order-3 magic hexagon. Very nicely illustrated.


• Meshalkin's Theorem generalizes Sperner's Theorem. We have an n-element set S. A k-composition of S is an ordered list (i.e., a sequence) of non-empty subsets, π = (S₁ , S₂ , ..., S_k) such that S = S₁ union S₂ union ... union S_k, and the subsets are pairwise disjoint. A k-composition antichain is a set of m different k-compositions,
      π₁ = (S_1,1 , S_1,2 , ..., S_1,k) ,
      π₂ = (S_2,1 , S_2,2 , ..., S_2,k) ,
      ... ,
      π_m = (S_m,1 , S_m,2 , ..., S_m,k) ,
  with the property that all the "first" sets (those in the first position in each composition – that is, the sets S_1,1 , S_2,1 , ..., S_m,1) are an antichain of S; and similarly all the "second" sets are an antichain; etc. up to the k-th sets.
  (There's a trick. "First" sets may repeat, as long as the entire composition doesn't repeat.)
  
  Theorem (Meshalkin). The number of k-compositions in a k-composition antichain (that is, the number m) is no greater than the largest multinomial coefficient of the form
      (n choose n₁ n₂ ... n_k)
  where n₁ + n₂ + ... + n_k = n.
  
  There's a precise description of the largest multinomial coefficient, which is a generalization of the unimodality theorem for binomial coefficients (Theorem 5.3.1). The theorem is:
  
  Theorem (Max Multinomial). For fixed positive integers n and k, the maximum multinomial coefficient of the form
      (n choose n₁ n₂ ... n_k)
  (where n₁ + n₂ + ... + n_k = n) occurs when every n_i = h or h+1, where h = [n/k] (the floor of n/k).
  
  Matt Beck and I found a nice proof of Meshalkin's theorem, similar to the proof of Theorem 5.3.3, which I hope to show you in class. (See "A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains", Journal of Combinatorial Theory Series A, volume 100 (2002), pages 196-199.)
  
  Questions:
  1. Find an example of a 2-composition antichain with general n. How is it related to antichains in the usual sense?
  2. Find an example of a 3-composition antichain with n = 4. How big can you make m? What is the upper bound given in the theorem? Can you find an example where m = this upper bound? If not, how close can you get?
  3. Prove the "Max Multinomial" theorem. (Not too easy, but not too hard. Think how we proved the unimodality of binomial coefficients.)


• Read about crook placements!

Corrections to Textbook

• In Exercise 2.16, the theorem is Theorem 2.3.1, not 3.3.1.
• In Exercise 2.28, a "block" is the part of a street between one corner and the next.
• Don't forget that Exercise 6.31 has two parts. One part is to show that a(n,k) has the formula given. 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 Exercise 7.51, the section should be 7.5, not 7.6.

Possible Term Projects

• P-1. Solve Ch. 1, # 4(b).


• P-2. Suppose a board B (possibly with missing squares) has an even number of squares, and every square has at least two neighboring squares. Is it always possible to cover the board perfectly with dominoes? If not, can you refine the conditions so it is possible? (You may add restrictions, or change them.)


• P-3. Prove or disprove that, in the chess master problem, Application 4 (problem F2), there is a sequence of days in which s/he plays exactly k games, for every value of k ≤ 77, but not for k > 77. Or at least, prove as much of this as you can, even if not all.


• P-4. Read up on Meshalkin's theorem and write a complete proof in your own words. (I will give you a couple of short papers to read.)


• P-5. Read up on the topic of "subset sums" (Problems 3.9 and F1). Discuss varying the numbers (number of people, maximum age) to see when two (disjoint) subgroups exist with equal age sums.


• P-6. Solve Problem G3. You might try to find a solution in the literature, and write it up in your own words, or you might be able to solve it yourself.


• P-7. For permutations of S_n², what is the relationship between the property of having no monotone sequence of length n+1 (as in Problem G2), and the inversion number or sequence?