Math 386: Combinatorics: Announcements

Fall 2022
Tom Zaslavsky

Index

• Test Grade Guidelines & Solutions
• Quizzes and Solutions
• Corrections to the Textbook
• Additions to the Textbook
1. Definitions
2. Terminology and Notation
3. Additional Problems
4. Supplements, Explanations, Hints

To the main class page | the schedule page | my home page.

Test 2 (11/28)

Final Exam (12/12)

• Quiz 1 (10/14) and solutions.
• Quiz 2 (11/2) and solutions.
• Quiz 3 (11/16) and solutions.
• Quiz 4 (12/5; ungraded) and solutions.

To the main class page | the schedule page | my home page.

Corrections to the Textbook

• Page 16, footnote 11: This is misleading. For example, ellipses are closed convex curves. Because two ellipses can meet in 4 points, the problem with ellipses will have a counting formula but it will not be the same one as for circles (and both are different from the count for straight lines).
• Page 27: The definition of a partition is nonstandard. Normally, a partition is defined to have non-empty parts. I will often mean that myself. Still, in this class we use the book's definition.
• Warning! If you look up a definition on line, or in another book, it will not always be the one we use. Rely on our book.
• Ch. 2, # 28: A block is a section of street between two cross streets, not a rectangular piece of city between streets. (Otherwise, "he walks 17 blocks to work" makes no sense.)
• Ch. 4, ## 39 and 50, have the same mistake. (X, ⊆) should be (P(X), ⊆). The set being partially ordered is not X, it is the power set P(X).
• Ch. 5, ## 44–45 seem to have a typographical error that I can't identify.
• Page 133, footnote 4: The sentence is not grammatical. It should read "called local finiteness, which". The name of a property is a noun, and "locally finite" is an adjective.
    (See below, "infinite p.o. set", for why an infinite p.o. set is relevant.)
• Ch. 6, # 33: The statement is backwards! The formula is for the number of ways to place k rooks in the forbidden squares. (Thus, it can be used to compute the number of ways to place n rooks in the allowed squares.)
• Do not use Theorem 5.5.1 for (x+y)^α; it's easy to misunderstand it and we don't need it. Use only the formula for (1+z)^α (middle of the page) and formula (5.22) for (1−z)⁻ⁿ.
• Page 191, formula for F_n(S) in the middle of the page: The cup should be a big cup.
• Ch. 6, # 35: "(1 ≤ k ≤ n)" should be "(1 ≤ m ≤ n)".
• Page 209, proof of (7.5): Since the induction has base case n = 0 and the induction step goes from n to n+1, the induction step must be for n ≥ 0, not n ≥ 1.
• Page 245: The equation 8 lines from the bottom should say "(2h₀ + 1)", not "(h₀ + 1)".
• Page 246: The equation 3rd line from the bottom says "−2xg(x) =" but the − is a mistake; it should be "2xg(x) =".
• Theorem 8.1.1: "positive" should be "non-negative".
• The Stirling numbers of the first kind and the notation s(n,k) are usually defined as what our book would call (−1)^n−ks(n,k). That's what you'll find in other sources (sometimes with other kinds of s's and even stranger notations). But we follow our book.
• Exercise 8.3: By "multiplication scheme" he means keeping the variables in the fixed order a₁a₂a₃a₄. Don't rearrange the variables!
• Exercise 8.36: "never go above" should be "never go below". (But you get the same number of paths.)
• Exercise 8.37 has some mistake. There are twice as many lattice paths as dissections. I'm not sure what the right question is.
    Also, the notation C_n should be R_n.
• Latin rectangles: The author says "based on Z_n" (pp. 385-386), but that only means his choice of symbol set. There is no modular arithmetic, so any symbol set can be used.

Additions to the Textbook

1. Definitions
   • C(n,k) := the number of k-combinations (k-element subsets) of an n-element set. (n, k are nonnegative integers.)
   • P(n,k) := the number of k-permutations (k-element ordered subsets) of an n-element set. (n, k are nonnegative integers.)
     Also, P(n) := P(n,n).
   • (n)_k := n(n−1)(n−2)···(n−[k−1]) (with k factors). (k is a nonnegative integer and n is any number, variable, etc.)
       In particular, (n)₀ := 1, since the product of no factors is defined as 1.
       Each (n)_k is a polynomial of degree k; that is why n can be anything that can go into a polynomial.
   • Binomial coefficient (n over k) := (n)_k/k!. (k is a nonnegative integer and n is any number, variable, etc.)
       This is different from the book's definition in Ch. 2, but in a later chapter Brualdi will change the definition to this one.
   • In a poset P, an interval [x,y] is defined as the set {z ∈ P : x ≤ z ≤ y}, i.e., the set of all elements between x and y, provided that x ≤ y. (This is just like an interval in the real line, but more general. We exclude the case where x is not ≤ y because then the set would be empty, and we don't want to call that an interval.)


2. Terminology and Notation
   • Use the word unique correctly. In mathematics, "unique" means "only one". It never means "different". If you mean that, say "different" or "distinct". I deduct points for incorrect usage.
       (In ordinary English "unique" basically means "unlike all others", which is similar to the mathematical meaning.)
   • Equivalent and equal do not mean the same thing. They are not "equivalent", especially when we get to equivalence relations.
   • The book defines the notation a <_c b to mean "a is covered by b". This c is not a variable, it is short for "cover". I will never use this notation.


3. Additional Problems
   1. The points-and-lines problem of Day 1. We have a set of 6 "points", or in general n points. We want to choose "committees" (subsets, traditionally called "lines") so the following properties are satisfied.
      • (o) No two lines are the same set.
      • (a) Every line has at least two points.
      • (b) Each pair of points belongs to exactly one line together.
      • (c) Each pair of lines has exactly one point in common.
      
      
   2. (N.B. We omitted this on Day 2. It will reappear in §3.3.)
      The colored triangles problem of Day 2. We have a small party with n = 4 or 5 or 6 people. They all know each other and each pair either likes each other, or dislikes each other. There may be a triple that all like each other, and there may be a triple that all dislike each other.
      1. Is it possible there are no liking triples AND no disliking triples?
      2. Is it possible (by carefully choosing whom to invite) to avoid having BOTH a liking and a disliking triple?
      
      
   3. In Exercise 3.9:
      1. Can 10 be replaced by 9?
      2. Can 10 be replaced by 5?
      3. What is the smallest number that 10 can be replaced by?
   
   
   4. In Newton's binomial theorem for (1 − x)^−1/2, simplify the binomial coefficients (−1/2 binom k) for k ≥ 0.
      1. Do very small values of k starting at 0.
      2. Then see if any pattern emerges; make a guess.
      3. Try to prove (or disprove) your guess.
      This is a good discussion problem; we'll share what you come up with.
   5. In Newton's binomial theorem for (1 − x)⁻², simplify the binomial coefficients (−2 binom k) for k ≥ 0. Write out the full series with a general term, using your simplification.
   
   

   Permutation patterns. Think of a permutation (a₁, a₂, ..., a_n) of {1, 2, ..., n} as the sequence of points (1,a₁), (2,a₂), ..., (n,a_n) in the xy-plane. Thus, a_i is the height of the i-th point. Each point is lower than some and higher than others; no two have the same height because all heights a_i are distinct numbers.
     A pattern shows relative heights of a subsequence of the permutation. For example, the pattern 132 means a subsequence whose second point is higher than the first, and whose third point is higher than the first but lower than the second. In the permutation 21534 (where n = 5), the subsequences 253, 254, 153, 154 are examples of the pattern 132, but 134 is not.

   6. Find all permutations of {1, 2, ..., n} that exclude the pattern 123, for n = 3, 4, 5. Do you see a system?
   7. For each n ≥ 3, find all permutations of {1, 2, ..., n} that exclude both the patterns 132 and 123. Hint: Start with n = 3 and 4. Then do n = 5. Do you see a system (it may not be easy)? If not, try n = 6; that can help.
   
   
   8. Prove Lemma. Assume n > r > 0. The Fibonacci numbers satisfy f_n = f_r+1f_n−r + f_rf_n−r−1. (This lemma is helpful for Ch. 7, ## 6, 7.)
   
   
   9. A problem in circle geometry related to §8.4.
      Draw a circle (it need not be perfect) and draw n points on it (not equally spaced). Draw all the chords (straight line segments) connecting the n points. Let h_n = the number of regions the chords cut the disk into.
      • Compute h₁ – oh, that's trivial. You get one region: h₁ = 1.
      • Compute h₂ by making the drawing with 2 points. You should get h₂ = 2.
      • Compute h_n for n = 3, 4, 5. Do you see a pattern and guess a formula?
      • Now test your guess against h₆. How is the guess doing?
      • If you compute h₇, can you refine your guess?
      
      Submit your results in class for discussion. (I'm not collecting written results.)
      • What values did you get for h_n (for the n's you did)?
      • What were your guesses for a formula?
      • Did you come to any conclusion about a formula?
      • Did you compare with the formula for h_n^(k) in §8.4? Does that help? Is there a value of k for which our h_n = his h_n^(k)? (You can test this by comparing values for small n's. That's often how new math discoveries are made.)
        I'm not saying you will find equality; not saying you won't.
   
   
   10. Simple Möbius functions (for experience).
       1. Find μ(x,y) for every pair x, y ∈ {1, 2, 3, ...} such that x ≤ y in the ordinary ordering of real numbers. There are infinitely many such pairs, but after computing a few examples you should see a simple pattern.
       2. Define L_n to be the poset {0, a₁, a₂, ..., a_n, 1} with the partial order relation determined by the following cover relations:
                  0 < a₁, a₂, ..., a_n,
                  a₁, a₂, ..., a_n < 1
          (therefore 0 < 1, by transitivity).
          Draw the Hasse diagram and calculate the Möbius function μ(0,1) for L_n with n = 2, 3, 4, ... until you see a general formula.
       3. Define M_n to be the poset {0, a₁, a₂, ..., a_n, A, b₁, b₂, 1} with the partial order relation determined by the following cover relations:
                  0 < a₁, a₂, ..., a_n,
                  a₁, a₂, ..., a_n < A < 1,
                  0 < b₁, b₂ < 1.
          (Don't forget to extend the cover relations to the full partial ordering using transitivity!)
          Draw the Hasse diagram and calculate the Möbius function μ(0,1) for M_n with n = 2, 3, 4, ... until you see a general formula.
   
   
4. Supplements, Explanations, Hints
   • Page 133, footnote 4: The main infinite partially ordered set we're interested in is N = {1,2,3,...} with the divisibility ordering. This is locally finite because ≤ is divisibility (written | ), so any interval {x : a ≤ x ≤ b} equals { x ∈ N such that a|x and x|b }, which is finite.
   
   
   • Hints for Ch. 6, #40:
     Hint #1: How do you describe a combination of a multiset? Think "submultiset". How do you describe a submultiset? Think "repetition numbers".
     Hint #2. You can do the problem directly, or you can see it as a continuation of Ch. 4, ##38–40.
     Hint #3. I always say, try a small example first. What's a small example here? k = 1 and k = 2 seem like good small examples.
   
   
   • Section 7.5: How to solve non-homogeneous linear recurrence relations using the characteristic polynomial. (The g.f. method is not involved in this discussion.) We assume the coefficients of the h_i are constant, the same as in Section 7.4.
     • Step 1: Get the general solution of the homogeneous equation. You will get a linear combination of exponentials with n-power coefficients (see Theorem 7.4.2). Each root r of the characteristic polynomial has a multiplicity, say s (possibly different for each root r). Remember this multiplicity s.
           Example: If the characteristic equation has roots 1 (once) and −2 (3 times), then the homogeneous general solution is
                   a₁1ⁿ + a₂(−2)ⁿ + a₃n(−2)ⁿ + a₄n²(−2)ⁿ.
       You remember 1 with multiplicity s=1 and −2 with multiplicity s=3.
     • Step 2: Look at the non-homogeneous part of the recurrence relation. It will be a sum of exponentials qⁿ with polynomial coefficients. (If you don't see any exponent, it means q=1; that is, you have 1ⁿ=1.) Remember e = (this degree) for each q.
           Example (continued): If the non-homogeneous part is n + 3·2ⁿ − 4n·(−4)ⁿ + 7·(−4)ⁿ, then you have 1ⁿ with coefficient polynomial of degree 1, 2ⁿ with coefficient polynomial of degree 0, and (−4)ⁿ with coefficient polynomial −4n+7 of degree 1. Remember the numbers e=1 for q=1, e=0 for q=2, e=1 for q=−4.
     • Step 3: If any of these values q is a root, remember the numbers s, s+1, ..., s+e. For the other q values from Step 2 remember the numbers 0, 1, ..., e.
     • Step 4: One solution to the non-homogeneous recurrence is a linear combination of exponentials qⁿ with coefficients nⁱ where i ranges over all the remembered numbers (for that q) from Step 3. We are only using the values q from Step 2 here.
           Example (continued): We had 1 with s = 1 (Step 1) and e = 2 (Step 2), totalling 3, so we form a linear combination of n·1ⁿ=n, n²·1ⁿ=n²; also (from Step 2) 2ⁿ; also (from Step 2) (−4)ⁿ, n·(−4)ⁿ. That will be
                   c₁n + c₂n² + c₃2ⁿ + c₄(−4)ⁿ + c₅n·(−4)ⁿ.
       You will never see such a big example in the course. It's big in order to illustrate all the possible aspects. Our problems will be much smaller.
     • Step 5: Substitute the linear combination from Step 4 into the recurrence and solve for the constants c₁, c₂, .... That gives you what we call a "particular solution" to the recurrence; call it H_n. It doesn't have to satisfy the initial conditions.
     • Step 6: Now add the general solution from Step 1 to H_n. This gives
                   h_n = a₁1ⁿ + a₂(−2)ⁿ + a₃n(−2)ⁿ + a₄n²(−2)ⁿ + H_n.
       Use the initial conditions to get the values of the unknown coefficients a₁, etc.
   
   

To the main class page | the schedule page | my home page.