# Math 386: Combinatorics Homework Assignments

## Fall 2003

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 (9/3)

Due Thurs. 9/4:

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

Due Fri. 9/5:

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

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

## HOMEWORK II (9/3)

Due Mon. 9/8:

Do ## 7, 11, 12, 15, 19, 22-24.

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

## HOMEWORK III (9/3)

Do for discussion on

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

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

## HOMEWORK IV (9/15)

Do for discussion on

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

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

Wed. 9/24: Ch. 5, ## 1-4, 8.
Thurs. 9/25: ## 5, 7, 15, 16.
Mon. 9/29: ## 17, and A1.
Wed. 10/1: ## 10 (again).

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

### Problem Set A

• A1. Prove combinatorially the formula in Ch. 5, #19: m2 = 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

Thurs. 10/9: ## 11, 13, 19, 22, 28, 30, 35, 37, and B2.
Fri. 10/10: ## 17, 23, 25, 31, 34, and B3.

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

Thurs. 10/16: Ch. 6, ## 1, 3, 4, 7, and # C1.
Fri. 10/17: Ch. 6, ## 8, 9, and # C2(a).

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 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.
• C3. 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 (10/9)

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

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

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

Wed. 10/29: Ch. 6, ## 10, 22, and # D1.

### Problem Set D

• D1. 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 (10/22)

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

Do for discussion on:

Wed. 11/5: Ch.\ 2, \#\# 1 (for k <= 21 and, if you can, k = 22).
Thurs. 11/6: Ch. 6, ## 23, 27, 29.
Ch. 2, ## 4, 5, 10, 18.
Fri. 11/7: Ch. 2, ## 1 (for k = 23), 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!)

Hand in Mon. 11/10:

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

## HOMEWORK SET XI (11/10)

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

Do for discussion on:

Thurs. 11/13: Ch. 2, ## 9, 14, 15, 17, 26, and ## E2, E4, E6.
Fri. 11/14: ## E1, E3, E5(a,b).

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

• E3. 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.

• E4. 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.

• 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 = n2 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:

Thurs. 11/20:
Ch. 2, ## 13, 20.
Ch. 5, # 40, also # F2(a,c).
Ch. 7, ## 1(a,b), 2, 3(a), 6, 15(a).
Fri. 11/21:
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 K7 --> K4, K3 ?
• 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:

Mon. 12/1: Ch. 7, ## 23(a,b), 24(a,c), 30, also # G1.
Wed. 12/3: Ch. 7, ## 23(b,d), 24(b,d), 29, also # G2.

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 K3) and no blue K4.

## 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:

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

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

Due Fri. 12/12:

Read Section 8.4 (and see correction to (8.23)).
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: 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!.

Go to announcements | course information.