Department of Mathematical Sciences
Binghamton University

Math 386: Combinatorics Homework Assignments

Fall 2011

Links to Homework Sets:
HW I || HW II || HW III || HW IV || HW V || HW VI || HW VII || HW VIII || HW VIIIa || HW IX || HW X || HW XI || HW XII || HW XIII

Do for discussion on Wed., 10/12:
Ch. 5, ## 4, 6, 8, 9 (error!), 21, 29(a).
# B1(a,b).

Hand in Fri., 10/14 Mon., 10/17:
Ch. 5, ## 7, 21, 29(b).
# B1(c).

Problem Set B

• B1.   Evaluate (that means, as an actual number) the following binomial coefficients. Look for patterns. Simplify.
  1. (5 choose 4), (4 choose 5), (5.6 choose 2).
  2. (0 choose 0), (0 choose 7).
  3. (−1 choose r) for r = 0, 1, 2, 3. Guess a general pattern for (−1 choose r). Prove it.

Do for discussion on
Wed., 10/26:
    Ch. 6, ## 5 & 27; 42.
    Ch. 7, ## 1-4, 17, 24.
    ## C4, C5.
Fri., 10/28:
    Ch. 6, ## 6 & 38; 29, 35; and C1.
    Ch. 7, ## 23, 26, 28, and C2.
    # C6.
Discussion continues on Monday with HW VIIIa; review on Tues.

Hand in Mon., 10/31:
    Ch. 6, ## 36, 49.
    Ch. 7, ## 16, 20, 21, 22, 27, and C3.

Problem Set C

• C1.   Multiply out the (n, i) entry of the matrix identity Ss = I (page 119, bottom). What formulas do you get? Then try the same with sS = I.
• C2.   Find the number of permutations of [8] in which:
  1. No integer is in its natural position.
  2. No odd integer is in its natural position.
  3. Exactly one integer is in its natural position.
  4. At most one integer is in its natural position.
• C3.   Find the number of permutations of [n] in which:
  1. Exactly k integers are in their natural positions.
  2. There are exactly k fixed points.
• C4. (-)   Find the number of inversions in these permutations:
  1. (5,8,2,1,4,6,3,7)
  2. (154)(3872)(6)
  3. (541)(8723)(6)
• C5. (-)   Compare the number of inversions in these pairs of permutations. Do you see a reason for the similarity?
  1. (541) and (321)
  2. (8723) and (4312)
• C6.   Write m = n − 1 in this problem. Consider the cyclic permutation (123...m). How many inversions does it have? Now, insert n in any one of the m possible places. How many new inversions are formed if you insert n
  1. before 1?
  2. right after 1?
  3. right after 2?
  4. after i, for any i ∈ [m]?
  If you solve this you may be ready for Ch. 6, #9.

Before Mon. 11/21, read the supplement on the missing text from Sect. 4.3, about the binomial series.

Hand in Mon. 11/21:
    Ch. 8, ## 17, 27, (omit 35: duplicate problem), 37, 40 (two ways), and # F2.

Problem Set F

• F1. Find closed expressions (no summations) for the following power series.
  1. ∑_n≥0 3n(n−1) xⁿ.
  2. ∑_n≥0 (n+5) xⁿ⁺².
  3. ∑_n≥2 2^n-1 xⁿ/n!.
• F2. Find a closed expression for ∑_n≥1 (2²ⁿ⁺¹/n! − 5^1-nn) xⁿ.

Read for Mon., 11/21: Sect. 14.1, and the supplementary pages on Stirling's approximation.

Do for discussion on:
Tues. 11/22:
    Ch. 8, # 30.
    ## G2, G3.
    Ch. 14, ## 2, 8.

Hand in Mon. 11/28:
    Ch. 8, ## 43, 49, 50.
    Ch. 14, ## 1, 7.
    ## G1(a), G4, G5.

Added afterwards: The answer to Ch. 8 #50 is on the announcements page.

Problem Set G

• G1. This question concerns Stirling's approximation. Compute an estimate for:
  1. C(m, (1/5)m).
  2. C(m, (2/5)m).
  3. C(m, (1/q)m) for any integer q > 2.
• G2. Concerning 132-avoiding permutations:
  1. How many are there in S₃? Use a result proved in the book.
  2. Now list them all. Find the left-to-right minima, and see what happens in between them. Look for patterns of behavior (thinking of the proof of Lemma 14.6).
• G3. The same as G2, but for S₄. (n = 4 is more interesting than n = 3, as n = 3 is too small to show much.)
• G4. Find the pattern-avoidance numbers S₂(12) and S₂(21) defined in Sect. 14.1.
• G4'. (Harder version of G4.) Find the pattern-avoidance numbers S_n(12) and S_n(21) for n > 2.
• G5. This problem ought to help you understand the proof of Lemma 14.6 on the structure of 123-avoiding permutations. See the definition of an ascent in Problem 8.50 (p. 178).
  1. Prove that an n-permutation is 123-avoiding if and only if it has no ascents except at its left-to-right minima.
  2. Use part (a) to list all the 123-avoiding 5-permutations that have exactly two left-to-right minima.
• G5'. (Corrected and expanded G5.) This problem ought to help you understand the proof of Lemma 14.6 on the structure of 123-avoiding permutations. See the definition of an ascent in Problem 8.50 (p. 178).
  1. Prove that an n-permutation is 123-avoiding only if it has no ascents except at its left-to-right minima.
  2. Use part (a) to list all the 123-avoiding 5-permutations that have exactly two left-to-right minima.
  3. List all the 132-avoiding 5-permutations that have exactly two left-to-right minima.
  4. Compare the permutations in the two lists, in view of the proof of Lemma 14.6.

Read for Wed., 12/7: Sect. 17.4. For a simpler explanation see my write-up on affine and projective planes and Latin squares.

Do for discussion on Wed. 12/7:
    Ch. 17, ## 10, 20, 22, 30.

Hand in Fri. 12/9 (changed):
    Ch. 17, ## 21, 25 (see definition), 30 (your best effort; see correction), 40 (see correction).

Do for discussion on Fri. 12/9:
    Ch. 17, ## 15, 38, and ## I1-2, I4.

There will be a review session on Sunday, where you can pick up your homeworks and Test III. I will also be in my office Tuesday afternoon at certain times.

Problem Set I

Problems I1 - I3 are thought problems. They are not essential to the class. They are good subjects for combinatorial thinking and I think the patterns you can find are interesting.

• I1. Look for a pattern in the remainders of the derangement numbers D_n, modulo m. Both the pattern itself and its length are worth thinking about.
  1. m = 3,
  2. m = 4,
  3. m = 5,
  4. m = 6,
  5. * m = 7, 8, 9, ..., as far as you wish to go. Do you see any general pattern at all by comparing the results for various values of m? (Hint: Possibly, the prime factorization of m has some influence.)
• I2. Prove the pattern(s) you found in I1.
• I3. (+) Prove that in # I1 there is always a finite repeating pattern, no matter what positive integer m is.
• I4. Using F = Z₅ (which, because 5 is prime, is one of the finite fields the author refers to in Sect. 17.4), find all the points and lines of:
  1. the affine plane over F, which I write AP(F);
  2. the projective plane over F, which I write PP(F).
  What I mean is: make a list of the points of AP(F), and list the lines of AP(F) in parallel families as I did in class for Z₃. I don't recommend a picture, as it gets very messy. Then:
  1. Count the points in each line, the lines on some one point, the number of lines in each parallel class, and the total number of lines. (This is to "get your hands dirty" by working with an actual example. It's instructive even though a bit boring; be glad I picked 5 instead of 11.) What are the parameters of the block design based on AP(F)?
  2. Find all the infinite points that are adjoined to AP(F) to make PP(F). Now the Count: How many points are there in each line?* What are the parameters of the block design based on PP(F)?
  3. Are there any parallel lines in PP(F)? What would parallelism mean in PP(F), anyway?

  * "One little point! Two little points! Three little points! Four wonderful little points! ..." (When does he stop?)