Math 386: Combinatorics Homework Assignments

Due Wed. 9/1:

Hand in Wed. 9/1: Ch. 1, ## 5, 9, 10.

HOMEWORK II

Due Fri. 9/3:

Hand in Tues. 9/7: Ch. 1, ## 13, 16, 25, 27

HOMEWORK III

Read Sects. 3.1-3.3.
Do for discussion on

Hand in Wed. 9/15 (changed!): Ch. 3, ## 4(c), 5(b), 12, 14.

HOMEWORK IV

Read Sects. 3.4-3.5.
Do for discussion on

Hand in Fri. 9/17: Ch. 3, ## 18, 20, 27, 33, 36, 38, 39(b).

HOMEWORK V

Read Sects. 5.1, 5.2, and 5.3 to (5.10).
Do for discussion on

Hand in Fri. 9/24: ## 6,8, 9, 11, 14, 18, and B2.

HOMEWORK VI

Read Sects. 5.3, 5.4, and 5.5. (In Sect. 5.4, emphasize clutters and Sperner's Theorem 5.4.3.)
Do for discussion on

Hand in Fri. 10/1: ## 20, 24, 32, and C3.

Problem Set B

• B1. Prove combinatorially the formula in Ch. 5, #19: m² = 2 C(m, 2) + C(m, 1).
• B2. Give a combinatorial proof of Chapter 5, #13.

Problem Set C

• C1. Prove Ch. 5, #22 combinatorially, assuming r, m, k are integers and r >= m >= k >= 0.
• C2. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of #10 or B2 or Pascal's formula might suggest an idea.)
• C3. Give a combinatorial proof of the first equation in Ch. 5, #7.

HOMEWORK VII

Read Sections 6.1-6.2.
Do for discussion on

Hand in Fri. 10/15: Ch. 6, ## 2, 5, and ## D2, D3.

HOMEWORK VIII

Read Sections 6.3-6.5.
Do for discussion on

Hand in Fri. 10/22: Ch. 6, ## 13, 14, 24(b), 26, 28, 30.

Problem Set D

• D1. Find the number of different ways you could get one dozen doughnuts at the bakery of Ch. 6, # 6, if the bakery has 9 apple-filled, 8 maple frosted, 5 chocolate, and 7 plain doughnuts, and
  (a) there is no further restriction;
  (b) the dozen must contain every type of doughnut.

  D2. Find the number of solutions to x₁ + x₂ + x₃ + x₄ = 22 in integers that satisfy x₁ <= 14, x₂ <= 8, x₃ <= 15, x₄ <= 7, and

  (a) all x_i >= 0;

  (b) all x_i > 0.

  D3. Find a formula for the number of r-combinations of the multiset M = {infty·a₁ , infty·a₂ , 100·a₃ , 100·a₄}, for all r >= 0. (``infty'' means infinity.)

Problem Set E

• E1. Let t be a positive integer and let M be the multiset {t·a₁ , t·a₂ , ..., t·a_k}. Find a formula for the number of r-combinations of M when:
  (a) r = 2t.
  (b) r = 2t + 1.
  (c) r = 2t - 1.
  Remember the Standard Hint: You may want to start with k = 3 (or even k = 2) to get an idea.

HOMEWORK SET IX

Read Section 2.1.

Do for discussion on:

Hand in Fri. 10/29: Ch. 2, ## 3, 6, 11, 17, 19.

Problem Set F

• F1 (a) In # 9, prove the same is true if there are 9 people in the room.
  (b) Prove that the conclusion does not necessarily follow if the number of people in the room is 6.
  (c) Can you decide whether or not it is possible to draw the same conclusion if there are 8 people in the room? 7 people? (This is probably hard. I would accept a solution as a term paper (optional, for extra credit). If you want to do that, discuss it with me first -- with no obligation.)

HOMEWORK SET X

Read Sections 4.1-4.4.

Do for discussion on:

Hand in Fri. 11/12: Ch. 4, ## 9, 15(a), 20, 24, 30

HOMEWORK SET XI

Read Sections 4.5 and 5.7 (see correction).

Do for discussion on:

Hand in Fri. 11/19:

Problem Set G

• G1. Consider the list of inversion sequences of permutations of S_n = {1,2,ldots,n} that comes from listing the permutations in the order given by the ``mobility'' process of Section 4.1 and then writing down their inversion sequences in the same order. Is there any interesting property of the specific order in which the inversion sequences appear in this list? I recommend you try generating the inversion sequences for very small values of n and see what turns up. If you find something interesting, you can report your observations, even if you don't know how to prove them.

The following problems are optional but are good mathematics. I don't know the answers. I'm very interested in what you come up with.

• G2. NEW What is the smallest number of inversions in a derangement of S_n = {1,2,...,n}, for each n >= 1? We conjecture that the answer might be the ceiling of n/2, but we're not sure.
• G3. NEW What is the largest number of inversions in a derangement of S_n? (Do Ch. 4, # 9 first.)
• G4. NEW Generalize Ch. 4, # 8, as far as possible. The general question is: given n, find a formula for the number of permutations having exactly k inversions, for all the several largest values of k. Specifically:
  (a) Do this for n = 5, where the single largest value of k is 15 and we already did k = 15, 14, 13 in # 8. Try to extend the same type of formula for smaller values of k. Don't expect one formula to work for all values of k; at some point the answer will get more complicated, but I'm asking you to find a simple formula that works for just the large k ("near" 15).
  (b) Try to develop a formula for any n. Here # 9 tells you the single largest value of k and asks you to find a solution for k = max - 1; I'm asking you to work down, i.e., k = max - 2, max - 3, and so on as far as you can find a simple formula.

HOMEWORK SET XII

Read Section 10.1 to the end of page 347. (See corrections.)

Do for discussion on:

Hand in Wed. 11/24: Ch. 10, ## 3, 8, 11, 12, 14-15(iii), and H2.

Problem Set H

• H1. Use Ch. 10 # 1 to find
  (a) the additive inverse (``negative'') of every element of Z<sub>4</sub> (i.e., do arithmetic mod 4);
  (b) the multiplicative inverse (``reciprocal'') of every element of Z₄ that has a reciprocal.

  H2. Use Ch. 10 # 3 to do the same as in # H1 for Z₅ (i.e., do arithmetic mod 5).

HOMEWORK SET XIII

Read Section 10.1 to the end of page 347.

Do for discussion on:

Problem Set I

• Recall that S_n = {1, 2, ..., n}.
• For n > 0, D(n) (this is a script D) is the set of all divisors of n, i.e., {m > 0 : m|n}. We partially order it by divisibility; i.e., we look at the poset (D(n), |).
• Also for n > 0, Pi_n is the poset of partitions of S_n , defined in Ch. 4, # 47.
• For a multiset X, C(X) (this is a script C) denotes the set of all combinations of X (as in Ch. 4, # 40), partially ordered by containment.

Every problem has the parts (a-c):

• I1. Do (a-c) for the poset Pi₃ .
• I2. Do (a-c) for the poset Pi₄ . (I1 and I2 are designed to give you a better idea of what Pi_n is in general.)
• I3. (A) Do (a-c) for D(12).
  (d) Compare this poset with the one in Ch. 5, # 45.
  (B) Do (a-c) for C(X) where X = { 2·a₁ , 1·a₂ }.
  (d) Compare this poset with those in (A) and Ch. 5, # 45.

  I4. (A) Do (a-c) for D(16).

  (d) What is special about this poset?
  (B) Do (a-c) for D(81).

  (d) Compare this poset with D(16).
  (C) Do (a-c) for C(X) where X = { 4·a₁ }.

  (d) Compare this poset with D(16).

  I5. (A) Do (a-c) for D(2^r), where r is any positive integer.

  (d) What is special about this poset?
  (B) Do (a-c) for D(3^r).

  (d) Compare this poset with D(2^r).

  I7. Do (a-c) for the poset (S₁₆ , |), that is, S₁₆ ordered by divisibility. (This is similar to Ch. 5 # 45).

  (d) Compare (S₁₆ , |) with D(16).

HOMEWORK SET XIV

Read Section 10.1, pp. 348-350 and Section 10.4 to the top of p. 384. ni Do for discussion on:

Hand in Wed. 12/8: Ch. 10, ## 13, 17(ii, v, vi), 41, 45, 48, and # J2.

Definitions

• Z_n , for an integer n >= 2, is the set {0, 1, ..., n-1} with arithmetic carried out modulo n. We call this system the integers modulo n.
• A polynomial f(x) with coefficients in Z_p is called irreducible over Z_p if it cannot be factored as a product of polynomials of lower degree. (Here we treat only the coefficients as elements of Z_p . x is an indeterminate, just as with ordinary polynomials.).
• F_q , for a prime power q = p^e (i.e., p is a prime number and e >= 1), is the set of all polynomials in i (or in x, if you prefer), with coefficients in Z_p , that have degree < e. Calculations in F_q are carried out modulo a fixed polynomial f(x) of degree e that is irreducible over Z_p . This polynomial is called a modulus polynomial for F_q . The meaning of ``calculating mod f(x)'' is that i satisfies the equation f(i) = 0. The system F_q is called a field of order q (that is, with q elements).
• For a prime number p, Z_p and F_p are the same. For any nonprime number, though, they are very different. (Z_n is not even a field, if n is not a prime.)

Problem Set J

• J1. This problem concerns the field F₉ of 9 elements, with modulus polynomial f(x) = x² + x + 2, as in the lecture.
  • (a) Write out the 9 elements of F₉ . Write the addition and multiplication tables.
  • (b) Find the negatives (additive inverses) and reciprocals (multiplicative inverses) of all elements that have them. Which inverses don't exist?
• J2.
  • (a) Construct 3 MOLS of order 9.
  • (b) For (a) you have to use the finite field F₉ of order 9. What is the difference that explains why you can't use the product-square construction of pp. 380-382 here although you could use it to find 2 MOLS?