Math 386: Combinatorics Homework Assignments

Due Fri. 9/5:

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

HOMEWORK II (9/3)

Due Mon. 9/8:

Hand in Wed. 9/10: Ch. 1, ## 13, 16, 25, 27

HOMEWORK III (9/3)

Read Sects. 3.1-3.3.
Do for discussion on

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

HOMEWORK IV (9/15)

Read Sects. 3.4-3.5.
Do for discussion on

Hand in Changed to Mon. 9/22: Ch. 3, ## 18, 20, 27, 33, 36, 38, 39(b).

HOMEWORK V (9/15)

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

Hand in Mon. 9/29: ## 6, 9, 10, 14, and 18.

Problem Set A

• A1. Prove combinatorially the formula in Ch. 5, #19: m² = 2 C(m, 2) + C(m, 1).

HOMEWORK VI (10/3)

For Wed. 10/8: Read Sects. 5.3-5. (In Sect. 5.4, emphasize clutters and Sperner's Theorem 5.4.3.)
Do for discussion on

Hand in Mon. 10/13: ## 18, 20, 24, 32, B1, and B4.

Problem Set B

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

HOMEWORK VII (10/9)

For Mon. 10/13: Read Sections 6.1-6.2. Do for discussion on

Hand in Mon. 10/20: Ch. 6, ## 2, 5, and ## C2(b), C3.

Problem Set C

• C1. 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;
  (c) the dozen must contain at least 2 maple frosted and 3 chocolate doughnuts.

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

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

HOMEWORK VIII (10/9)

For Mon. 10/20: Read Sections 6.3-6.4.
Do for discussion on

Hand in Mon. 10/27: Ch. 6, ## 13, 14, 24(b), 26.

HOMEWORK IX (10/22)

For Mon. 10/27: Read Section 6.5.
Do for discussion on

Problem Set D

• D1. 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: Try small cases. You may want to start with k = 3 (or even k = 2) to get an idea.

HOMEWORK SET X (10/22)

For Mon. 11/3: Read Section 2.1 to Application 5 (inclusive).

Do for discussion on:

Hand in Mon. 11/10:

HOMEWORK SET XI (11/10)

Read Sections 2.1 (to end) and 2.2. (See correction to Application 9.)

Do for discussion on:

Hand in Mon. 11/17: Ch. 2, ## 3, 17, 23, 27, and # E5(c).

Problem Set E

• E1.(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?
  
  

  E2. By X_n I mean the statement that, if there are 10 people whose ages lie between 1 and n, then there exist two subgroups of the 10 people, having no members in common, such that both subgroups have the same sum of ages. The problem in the book is to show that X₆₀ is true.

  (a) Show that X_n is true for n = 61, 62, ... for as far as you can prove it. See how high you can get!

  (b) Find a value of n (it doesn't matter how large!) for which X_n is false: that is, if the ages of the 10 people are limited to between 1 and n, it is possible to find a selection of ages such that no two subgroups have the same age sum.

  
  

  E3. Consider the set Z₃₂ = {0, ..., 31}. In the codebook of spy ``X'', some of the numbers in Z<sub>32</sub> are colored red, some of them are black, but of course you don't know which ones; you don't even know how many are red. Let's suppose you color Z<sub>32</sub> with red and black; call your coloring ``good'' if your colors agree with X's on at least half the numbers. Here's a way to get a new coloring from an old one, called ``shifting (to the left) by c'' (where c is in Z₃₂): the shifted color of a is the original color of a + c (if a + c >= 32, then you take the remainder after division by 32). For instance, if you color 1, 7 red and the rest black, and shift by 3, then in the shifted coloring 4 is red and so is 30 (since 7 = 4 + 3 is red and 30 + 3 = 33 reduces to 1, which is red, upon division by 32). Prove that if you color the numbers in Z₃₂ so half are red and half black, then there is a number c (but we don't know what it is) such that your coloring shifted by c is good.
  
  

  E4. Concerning Application 9, here are some sequences of N = n² + 1 numbers. For each sequence, find m₁, m₂, ..., m_N (defined in the book) and find a longest increasing subsequence. Then find a value m such that more than n different m_i's equal m, if such an m exists. If m exists, use it to find a decreasing subsequence longer than n. If no m exists, use the m_i's to find an increasing subsequence longer than n.

  (a) n = 3, and the sequence is 3, -1, -pi, pi, 3.2, 1.88, 3, 0, 14, 7.

  (b) n = 3, and the sequence is 5, 9, -2, 0, -1, -4, 55, 44, 22, 23.

  (c) n = 3, and the sequence is 5, 9, -2, 55, -1, -4, 0, 44, 22, 23.
  
  

  E5. Find a sequence of N numbers that has no increasing and no decreasing subsequence of length n + 1, where

  (a) n = 3, N = 9;

  (b) n = 4, N = 16;

  (c) N = n² for any n >= 1.
  
  

  E6. In connection with Application 4, solve as many values of k >= 22 as you can.

HOMEWORK SET XII (11/10)

Read Section 2.3 (except the material on t-element subsets on pages 40-41), Section 5.6 (omit the square root of 20 on page 149), and Section 7.1.

Do for discussion on:

Ch. 2, ## 13, 20.

Ch. 5, # 40, also # F2(a,c).

Ch. 7, ## 1(a,b), 2, 3(a), 6, 15(a).

Ch. 2, # 21 (if ambitious).

# F3(a,d).

Ch. 7, ## 1(c), 3(c), 4, 15(d).

Hand in Mon. 11/24 (Revised due date: Wed. 11/26 at 1:00 p.m.):

Ch. 2, ## 23, 27.

Ch. 7, ## 1(d), 3(d), 7.

## F1, F2(b), F3(b,c).

Problem Set F

• F1. Does K₇ --> K₄, K₃ ?
• F2. For use in the binomial series, ``evaluate'' (or ``simplify'') the binomial coefficients (r choose n) for all n > 0 s and for:
  • (a) r = -1. Try to do it both directly and via Ch. 5, # 21.
  • (b) r = -k, where k is any positive integer. Again, do it both directly and via Ch. 5, # 21.
  • (c) r = 1/2. (This is in the book, but you should try to do it for yourself. Hint: n = 0 and n = 1 should be treated as special cases. Maybe also n = 2.)
• F3. Substitute your answers from # F2 in the binomial series and simplify to see what you get for the following expressions:
  • (a) (1-x)^-1.
  • (b) (1-x)^-2.
  • (c) (1-4x)^-1/2 (here you can use the simplified binomial coefficient I showed in class, or work it out yourself).
  • (d) (1-4x)^+1/2 (here, use the simplified binomial coefficient from F3(c)).

HOMEWORK SET XIII (11/10)

Read Section 7.4; Section 7.2 to the top of p. 204 (to learn what is a ``linear recurrence relation with constant coefficients,'' both homogeneous and nonhomogeneous).

Do for discussion on:

Hand in Mon. 12/1 (not 12/2): Ch. 7, ## 23(e), 24(e), 31.

Problem Set G

• G1. (Variant of Application 8) Supppose you have n colors and two disks of n sectors each, a fixed outer disk and a rotatable inner disk. You color the sectors of the outer disk so they all have different colors, and you color the sectors of the inner disk any way you like. Prove that there is a way of aligning the sectors so that at least one outer sector is lined up with an inner sector of the same color.
• G2. Prove that r(3,4) > 8 by showing that it is possible to color the line segments joining 8 points in the plane in two colors, red and blue, so that there is no red triangle (red K₃) and no blue K₄.

HOMEWORK SET XIV (12/5)

Read Sections 7.5 (you will not be tested on pp. 232-234), 7.6, and 8.1.

Do for discussion on:

Hand in Thurs. 12/11: Ch. 7, ## 25(e), 33, and Ch. 8, ## 2, 4(b) (see the correction).

Due Fri. 12/12:

To read more about the many dozens of different things that Catalan numbers count, you can glance through Richard Stanley's Web page: here are links to his notes in PDF format and in PostScript format.

Problem Set H

• H1. In Ch. 6, # 30, prove:
  1. The number of linear permutations of M = { 2·a, 3·b, 4·c, 5·d } equals 13!/2!3!4!5!.
  2. The number of linear permutations of M' = { aa, 3·b, 4·c, 5·d } equals 12!/3!4!5!. (aa is a single element composed of two a's.)
  3. The number of linear permutations of M'' = { aa, bbb, 4·c, 5·d } equals 10!/4!5!.