Math 386: Combinatorics Homework
Assignments IX - XIII

Fall 2006

For Mon., 10/30: Read Sections 6.1-6.2.
For Wed., 11/1: Read Section 6.3 to p. 175.

Do for discussion on
Thurs., 11/2: Ch. 6, ## 1, 3, 4, 6, 7, and # E1.
Fri., 11/3: Ch. 6, ## 8, 9, 12, 17, and ## E2(a), E4.

Hand in Mon., 11/6: Ch. 6, ## 2, 5, 14, 29, and ## E2(b), E3, E5.

E1. 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
1. there is no further restriction;
2. the dozen must contain every type of doughnut;
3. the dozen must contain at least 2 maple frosted and 3 chocolate doughnuts.
E2. Find the number of solutions to x₁ + x₂ + x₃ + x₄ = 22 in integers that satisfy
x₁ ≤ 14, x₂ ≤ 8, x₃ ≤ 15, x₄ ≤ 7, and
1. all x_i ≥ 0;
2. all x_i > 0.
E3. 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, as you probably suspected.)
E4. How many numbers from 799 to 11000 (inclusive) are not divisible by either 8 or 14?
E5. Given integers a and b, 0 < a < b, how many numbers from a to b (inclusive) are not divisible by either 10 or 15?

For Mon., 11/6: Read Sections 6.3-6.5.

Do for discussion on
Thurs. 11/7: Ch. 6, ## 10, 11, 15, 16, 24(a).
Fri. 11/8: Ch. 6, ## 13, 19, 22, 24(b), 26, 27.

Hand in Mon., 11/11: Ch. 6, ## 21, 23, 25, 31, 32.

For Mon. 11/13: Read Section 2.1 (omit Application 6).

Do for discussion on
Thurs. 11/14: Ch. 2, ## 1, 4, 5, 7.
Fri. 11/15: Ch. 2, ## 2, 3, 9, 16 (see correction), 18, 26.

Hand in Mon. 11/20:
Ch. 6, ## 24(c), 30.
Ch. 2, ## 1 (for k = 23), 6, 10, 11, 15, and F1.

For Mon., 11/20: Read Section 2.2.

Do for discussion on:
Wed. 11/22: Ch. 2, ## 8, 13, 14, 28, F2(a,b).

Hand in Mon. 11/27: Ch. 2, ## 1 (for k = 24), 17, 19, 27, and F2(c), F3.

F1. This concerns Ch. 2, #9.
1. Prove the same conclusion is true if there are 9 people in the room.
2. Prove that the conclusion does not necessarily follow if the number of people in the room is 6.
3. Can you decide whether or not it is possible to draw the same conclusion if there are 8 people in the room? 7 people?
F2. 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.
1. n = 3, and the sequence is 3, -1, -pi, pi, 3.2, 1.88, 3, 0, 14, 7.
2. n = 3, and the sequence is 5, 9, -2, 0, -1, -4, 55, 44, 22, 23.
3. n = 3, and the sequence is 5, 9, -2, 55, -1, -4, 0, 44, 22, 23.
F3. Find a sequence of N numbers that has no increasing and no decreasing subsequence of length n + 1, where
1. n = 3, N = 9;
2. n = 4, N = 16;
3. N = n² for any n ≥ 1.

For Mon., 11/27: Read Section 10.4 to the middle of page 395. Section 1.5 is optional background reading for Section 10.4.

Do for discussion on:
Wed. 11/29: Ch. 10, ## 37 and G1, G2.

G1.
1. Construct the Latin square of order 3, in standard form, that is the addition table of Z₃.
2. Is there any other Latin square of order 3 that is in standard form? If so, how many can you find?
G2.
1. Construct the Latin square of order 4, in standard form, that is the addition table of Z₄.
2. Is there any other Latin square of order 4 that is in standard form? If so, how many can you find?

TEST III is on Thursday, Nov. 30.