Math 386: Combinatorics Homework Assignments

Go to announcements | course information.

General Advice
on homework problems

Besides finding the anwer, always try to explain, as well as you can, how you know you have the correct answer.

When solving problems, a systematic solution is better than guesswork. You often may find a solution by intelligent guessing, but then you should look for a way of showing that your solution is correct. This part needs to be systematic if it is to be completely convincing. (This will be clearer after a few days of class!)

Allow 15 minutes per problem (minimum) before you give up, even if you feel you're getting nowhere. These problems need time for thought. If you're still stuck, go on to another problem. Return to the sticky problem later (say, the next day). Often, it then looks easier because you tried hard the first time and then gave your mind time to grind it up--I mean, to come up with ideas. To get the advantage of this method, you have to start the problems well ahead of time. Last-minute effort will not work well in this class.

Rules for hand-in homework.

  1. Hand in a final draft: neat work that is well organized and not cramped. Use as much space as you need. Please also leave some extra space between problems for my comments.
  2. You may discuss hand-in HW with other people, but you must write it up in your own words.
  3. No little stubbies from tearing a page out of your binder. Remove them neatly, please!
  4. Fasten the pages securely. Staples are best. Folding the paper over and/or tearing it is no good (not secure); paper clips don't hold well.

HOMEWORK I

Due Thurs. 9/5:

Read Sect. 1.1.
Do (for class discussion) Ch. 1, ## 1-3.

Due Fri. 9/6:

Read Sect. 1.2.
Do Ch. 1, ## 4(a), 8, 26.

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

HOMEWORK II

Due Mon. 9/9:

Read Sects. 1.3, 1.5.
Do ## 7, 11, 12, 15, 19, 22-24.

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

HOMEWORK III

Read Sects. 3.1-3.3.
Do for discussion on

Thurs. 9/12: Ch. 3, ## 1-8, 10, 13.
Fri. 9/13: Ch. 3, ## 9, 11, 15.

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

HOMEWORK IV

Read Sects. 3.4-3.5.
Do for discussion on

Thurs. 9/19: Ch. 3, ## 16, 17, 19, 21, 25.
Fri. 9/20: Ch. 3, ## 23, 24, 30, 32, 37, 39(a).

Hand in Mon. 9/23: 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

Wed. 9/25: Ch. 5, ## 1-4, 10.
Thurs. 9/26: ## 5, 7, 15, 16.
Fri. 9/27: ## 17, and A1.

Hand in Mon. 9/30: ## 6,8, 9, 11, 14, 18, and A2.

HOMEWORK VI

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

Wed. 10/2: Ch. 5, ## 1-5, 7, 10, 13, 15, 16, and A1.
Thurs. 10/3: ## 11, 19, 22, 28, 30, 35, 37, and A3.
Fri. 10/4: ## 17, 23, 25, 31, 34, and A4.

Hand in Mon. 10/7: ## 13 (again), (not 18 - cancelled), 20, 24, 32, and A5 and (added) A2.

Problem Set A

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

    HOMEWORK VII

    Read Sections 6.1-6.2.
    Do for discussion on

    Wed. 10/16: Ch. 6, ## 1, 3, 4, 7, and # B1.
    Thurs. 10/17: Ch. 6, ## 8, 9, and # B2(a).

    Hand in Mon. 10/21: Ch. 6, ## 2, 5, and ## B2(B), B3.

    Problem Set B

    • B1. 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.
    • B2. Find the number of solutions to x1 + x2 + x3 + x4 = 22 in integers that satisfy x1 <= 14, x2 <= 8, x3 <= 15, x4 <= 7, and
      (a) all xi >= 0;
      (b) all xi > 0.
    • B3. Find a formula for the number of r-combinations of the multiset M = {infty·a1 , infty·a2 , 100·a3 , 100·a4}, for all r >= 0. (``infty'' means infinity.)

    HOMEWORK VIII

    Read Sections 6.3-6.4.
    Do for discussion on

    Thurs. 10/24: Ch. 6, ## 11, 15-17, 24(a), 25.
    Fri. 10/25: Ch. 6, ## 12, 19-21, 24(c).

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

    HOMEWORK IX

    Read Sections 6.5 and 2.1 to Application 4 (inclusive).
    Do for discussion on

    Thurs. 10/31: Ch. 6, ## 10, 22, and # C1.
    Ch.\ 2, \#\# 1 (for k <= 21 and, if you can, k = 22), 4, 10.
    Fri. 11/1: Ch. 6, ## 23, 27, 29.
    Ch. 2, ## 1 (for k = 23), 5, 18.

    Hand in Mon. 11/4:

    Ch. 6, ## 28, 30.
    Ch. 2, ## 6, 11, 19.

    Problem Set C

    • C1. Let t be a positive integer and let M be the multiset {t·a1 , t·a2 , ..., t·ak}. 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

    Read Section 2.1, Application 5.

    Do for discussion on:

    Mon. 11/4: Ch. 2, ## 2, 9, 16.
    In #16, assume that acquaintanceship is symmetric: i.e., if A is acquainted with B, then B is acquainted with A. (This isn't always so in real life!)
    Wed. 11/6: # 7.

    HOMEWORK SET XI

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

    Do for discussion on:

    Thurs. 11/14: Ch. 2, ## 9, 14, 15, 17, 26, and ## D2, D4, D6.
    Fri. 11/15: ## D1, D3, D5(a,b).

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

    Problem Set D

    • D1.(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?
    • D2. By Xn 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 X60 is true.
      (a) Show that Xn 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 Xn 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.

    • D3. Consider the set Z32 = {0, ..., 31}. In the codebook of spy ``X'', some of the numbers in Z32 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 Z32 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 Z32): 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 Z32 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.

    • D4. Concerning Application 9, here are some sequences of N = n2 + 1 numbers. For each sequence, find m1, m2, ..., mN (defined in the book) and find a longest increasing subsequence. Then find a value m such that more than n different mi'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 mi'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.

    • D5. 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 = n2 for any n >= 1.

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

    HOMEWORK SET XII

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

    Do for discussion on:

    Thurs. 11/21:
    Ch. 2, ## 13, 20.
    Ch. 5, # 40, also # E3(a,c).
    Ch. 7, ## 1(a,b), 2, 3(a), 6, 15(a).
    Fri. 11/22:
    Ch. 2, ## 21 (if ambitious).
    # E4(a,d).
    Ch. 7, ## 1(c), 3(c), 4, 15(d).

    Hand in Mon. 11/25:

    Ch. 2, ## 23, 27.
    Ch. 7, ## 1(d), 3(d), 7.
    ## E2, E3(b), E4(b,c).

    Problem Set E

    • E1. (The Strohmenger 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.
    • E2. Does K7 --> K4, K3 ?
    • E3. For use in the binomial series, ``evaluate'' (or ``simplify'') the binomial coefficients (r choose n) for all n > 0 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.)
    • E4. Substitute your answers from # E3 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 H1(c)).

    HOMEWORK SET XIII

    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);
    Section 7.5 (you will not be tested on pp. 232--234).

    Do for discussion on:

    Wed. 11/27: Ch. 7, ## 23(a,b), 24(a,c), 25(a,b), 30, also # E1
    Mon. 12/2: Ch. 7, ## 23(b,d), 24(b,d), 25(c,d), 29, also # F1

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

    Problem Set F

    • F1. Prove that r(3,4) > 7 by showing that it is possible to color the line segments joining 7 points in the plane in two colors, red and blue, so that there is no red triangle (red K3) and no blue K4.

    HOMEWORK SET XIV

    Read Sections 7.6, the last page of 5.6, and 8.1.

    Do for discussion on:

    Wed. 12/11:
      Ch. 7, ## 26, 32, 34 (recommended challenge problem)
      Ch. 8, ## 1, 4(a)
    Thurs. 12/12: Ch. 8, ## 3, 5 (optional challenge problem)

    Hand in Thurs. 12/12: Ch. 7, # 33, and Ch. 8, ## 2, 4(b)

    Due Fri. 12/13:

    Read Section 8.4.
    Do for discussion: Ch. 8, # 29

    To read more about the many dozens of different things that Catalan numbers count, you can glance through Richard Stanley's Web page:

    PDF format;
    PostScript format.

    Go to announcements | course information.