Department of Mathematical Sciences
Binghamton University

Math 386: Combinatorics Homework Assignments

Fall 2010

Go to rules for homework | announcements | course information | syllabus.

HOMEWORK I (8/30)

Due on Tues., 8/31:
Read Ch. 1 intro, Sect. 1.1, beginning of Sect. 1.2.
Do (for class discussion) Ch. 1, ## 1, 2, 3, 5, 10.

Due on Wed., 9/1:
Read Sect. 1.2.
Do (for discussion) Ch. 1, ## 2(again), 12, 14, 16, 17.
Continue to think about the problem of perfectly covering by dominoes a 3×5 board with the center square cut out.
Also, continue to study how the proof by coloring works, for proving that a 6×6 board cannot be perfectly covered by tetrominoes.

Due on Fri., 9/3:
Read Sect. 1.4, 1.6.
Do (for discussion) Ch. 1, ## 15, 22, 24, 38, and A1.

Hand in Mon., 9/13:
Ch. 1, ## 4(a), 7, 21, A2, A3.

Extra! Extra! Much more about magic squares in only 5 pages.

Problem Set A

A1. How many Latin squares of order 2 are there?
A2. What is the difference between a magic square and a Latin square? Better question: How many differences can you list?
A3. Following the procedure in Problem 1.16 in the book, do you still get a magic square if you allow the original square to have any n² distinct integers? [Added later: Apologies. A3 is not well stated. I meant: Define a "relaxed magic square" to be just like a magic square, except that you can use any distinct integers you wish instead of the integers 1,2,...,n². Suppose you have a relaxed magic square of order n. Then replace each number a_ij in the square by n² - a_ij . Do you still have a relaxed magic square?]

HOMEWORK II (revised 9/2)

Due on Mon. 9/13:
Read Sect. 2.1-2.
Do (for discussion) Ch. 2, ## 2, 4(a).

Due on Tues. 9/14:
Do (for discussion) Ch. 2, ## 1, 3, 4(b), 5(a), 7, 8.

Due on Wed. 9/15:
Do (for discussion) Ch. 2, ## 6, 10.

Hand in Wed., 9/15:
Ch. 1, ## 8, 9.
Ch. 2, ## 4(c), 5(b), 9.

Here is an entire article on magic hexagons of order 3, if you want to read more about them.

HOMEWORK III (9/15)

Read Sects. 2.3-5.
(Reading part of Sect. 2.6 is recommended. It will not be tested. It may help you understand reasons for counting.)

Do for discussion on
Tues. 9/121: Ch. 2, ## 11, 13.
Wed. 9/22: Ch. 2, ## 16, 17, 19(a), 22.

Hand in Fri. 9/24: Ch. 2, ## 15, 19(b), 28.

HOMEWORK IV (9/15)

Read for Mon., 9/27: Sects. 5.1-2.

Do for discussion on
Tues., 9/28: Ch. 2, ## 31, 34, 41, 60.
Wed., 9/29: Ch. 2, ## 39, 48, 63; Ch. 5, # 2.
Fri., 10/1: Ch. 2, # 50; Ch. 5, ## 1, 3.

Hand in Mon., 10/4 (changed):
Ch. 2, ## 40, 51, 64(a).

HOMEWORK V (9/30)

Read for Mon., 10/4: Sects. 5.2 and 5.4.

Do for discussion on
Mon., 10/4: Ch. 5, ## 1-3, 4-6, 7-8, 15, and especially B2.
Tues., 10/5: Ch. 5, ## 9, 16, 23, 39, and especially B3.
Wed., 10/6: Ch. 5, ## 18, 24. (Revised.)

Hand in Fri., 10/9: # B1 and Ch. 5, ## 10, 13, 25, 37.

Problem Set B

B1. Prove combinatorially the formula in Ch. 5, #19: m² = 2 (m choose 2) + (m choose 1).
B2. Prove combinatorially that (n choose k) = (n choose n-k) for n ≥ k ≥ 0.
B3. Write from memory a combinatorial proof of Pascal's Formula:
(n choose k) = (n-1 choose k) + (n-1 choose k-1) for n > k > 0.
(If you can't remember it, look it up in Ch. 2 and then reproduce it with the book closed.)
Then extend the combinatorial proof to cover all the cases where k, n ≥ 0. How do you handle these cases?

HOMEWORK VI (10/5)

Read for Fri., 10/8: Sect. 5.5 up to the end of page 148 (corrected).

Do for discussion on
Fri., 10/8: Ch. 5, # 14 (don't assume k ≤ r), also ## B1 (this is a hand-in; keep a copy of your proof when you submit it) and C1.
Mon., 10/11: Ch. 5, ## C2, C3, C4.

Problem Set C

C1. Evaluate (that means, as an actual number) the following binomial coefficients. Look for patterns. Simplify.
1. (5 choose 4), (4 choose 5), (5.6 choose 2).
2. (0 choose 0), (0 choose 7).
3. (7 choose −1), (0 choose −1).
4. (−1 choose r) for r = 0, 1, 2, 3. Can you guess a general pattern for (−1 choose r) (no proof required)?
5. (−1/2 choose r) for r = 0, 1, 2, 3. Can you guess a general pattern for (−1/2 choose r) (no proof required)?
C2. Find and prove a simple formula for (−1 choose n), n ≥ 0. Use your formula to find a simple power series expansion of 1/(1-x).
C3. Find and prove a simple formula for (−1/2 choose n), n ≥ 0. Use your formula to find a simple power series expansion of (1-x)^-1/2.
C4. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of #10 or #B1 or Pascal's formula might suggest an idea.)

TEST I is on Tuesday, Oct. 12. It will cover everything we've done up to that time (Homeworks I-VI) except power series (in Sect. 5.5).

HOMEWORK VII (10/14)

Read for Fri., 10/15: Sect. 6.1.

Read for Mon., 10/18: Sect. 6.2.

Do for discussion on
Tues., 10/19: Ch. 5, # 19; also Ch. 6, ## 1, 3, 4.
Wed., 10/20: Ch. 5, # 22; also Ch. 6, ## 7, 10, 11, and # D1.

Hand in Fri., 10/22: Ch. 5, # 20 (simplify your answer as far as you can); also Ch. 6, ## 5, 8, 17; also # D2.

Problem Set D

Here are two simple problems in an area of combinatorics called "extremal set theory". You can read more about it in Section 5.3.

D1. What is the largest number of combinations of an n-element set that can be chosen, so that any two chosen combinations have empty intersection?
D2. What is the largest number of combinations of an n-element set that can be chosen, so that no two chosen combinations have empty intersection?

HOMEWORK VIII (10/21)

Read for Fri., 10/22: Sect. 6.3. (For more on Stirling's approximation see the additions to textbook.)

Read for Mon., 10/25: Sects. 6.4, 7.0, 7.1 to the middle of page 210.

Do for discussion on
Tues., 10/26: Ch. 6, ## 12, 16, 24(a), 25, 30; Ch. 7, # 1(a); and ## E1, E3.
Wed., 10/27: Ch. 6, ## 14, 20, 24(b), 33 (see corrective note); Ch. 7, # 1(b); and ## E4, E5.

Hand in Fri., 10/29: Ch. 6, ## 21, 24(c), 29; Ch. 7, #3(a); and # E2.

Problem Set E

E1. Find the number of solutions to x₁ + x₂ + x₃ + x₄ = 22 in integers that satisfy
x₁ ≤ 14, x₂ ≤ 14, x₃ ≤ 14, x₄ ≤ 7, and
1. all x_i ≥ 0;
2. all x_i > 0.
E2. Find a formula for the number of r-combinations of the multiset
M = {infty·a₁ , infty·a₂ , 100·a₃ , 100·a₄},
for all integers r ≥ 0. ("infty" means infinity, as you probably suspected.)
E3. Given a positive integer k and integers a, b that satisfy 0 < a < b, how many numbers from a to b (inclusive) are divisible by k? (This is to help you with # E4.)
E4. Given integers a and b, 0 < a < b, how many numbers from a to b (inclusive) are not divisible by either 10 or 15? (See # E5.)
**E5. How many ways are there to place ceiling(n/2) nonattacking crooks (i.e., the maximum number) on an n × n triangular board? (Read about it.)

HOMEWORK SET IX (10/22)

Read for Fri., 10/29: Sects. 5.6 except p. 149 (this is the time to review it), 7.1-2.

Read for Mon., 11/1: Sect. 7.4.

Do for discussion on:
Tues. 11/2: # C2 (both parts); # F1(a,b,c); and Ch. 7, ## 1(c), 2, 3(b), 8, 13(a-c), 14(a-c), 17.
Wed. 11/3: # F1(d,e); and Ch. 7, ## 5, 6, 10, 11, 34 (changed: due today).

Hand in ~~Fri. 11/5~~ Mon. 11/8 (changed):
Ch. 7, ## 1(d), 4, 13(d), 14(d,e), 33 (using g.f.); also ## C1(e), C3 (both parts), and # F2(b).

Problem Set F

F1. Look for a pattern in the remainders of the derangement numbers D_n, modulo m. Both the pattern itself and its length are worth thinking about.
1. m = 3,
2. m = 4,
3. m = 5,
4. m = 6,
5. * m = 7, 8, 9, ..., as far as you wish to go. Do you see any general pattern at all by comparing the results for various values of m? (Hint: Possibly, the prime factorization of m has some influence.)
F2. Prove the pattern(s) you found in F1.
F3. * Prove that in F1 there is always a finite repeating pattern, no matter what positive integer m is.

HOMEWORK SET X (10/22, revised 11/5)

Read for Mon., 11/8: Sects. 7.5-6.

Do for discussion on:
Tues. 11/9: Ch. 7, ## 37, 43(both methods), 46 (by g.f.), 48(e), 50.
Wed. 11/10: Ch. 7, ## 41 (the diagonals here cannot meet at their endpoints), 52 (by g.f.), 53.

Hand in Fri. 11/12:
Ch. 7, ## 7 [Solution available!], 14(e) (now find a formula for h_n), 48(c), 51; and # F3 (if you can do it).

HOMEWORK SET XI (11/5, rev. 11/11)

Read for Fri., 11/12: Sect. 8.1.

Read for Mon., 11/15: Sect. 8.2 to the top of page 281.

Do for discussion on:
Tues. 11/16: Ch. 7, # 48(f); Ch. 8, # 3, 4(a), 6, 7; and G1, G2, G5.
Wed. 11/17: Ch. 8, ## 2, 4(b), 9, 10.

Hand in Fri. 11/19:
Ch. 7, # 48(e); Ch. 8, ## 1, 5, 8; and G3, G4, G6.

Problem Set G

G1. Calculate the Catalan numbers C₁₁ and C₁₂ using formulas and data in Section 8.1.
G2. In a multiplication scheme for a₁, a₂, ..., a_n, how many parentheses are there?
G3. Find the triangulation of a convex polygon that corresponds to each of the following multiplication schemes:
(a) (( a₁ (( a₂ a₃ ) ( a₄ a₅ ))) a₆ ).
(b) (( a₃ (( a₂ a₅ ) ( a₄ a₆ ))) a₁ ).
G4. In # G3, compare the two parts (questions and answers). What is the effect of permuting the variables a_i?
G5. Let h_n denote the number of multiplication schemes for n numbers, disregarding the order of the numbers. What is h_n?
G6. * Find a bijection between the multiplication schemes for n numbers a₁, a₂, ..., a_n, taken in that order, and the acceptable sequences of n-1 +1's and n-1 -1's.

HOMEWORK SET XII (11/15)

Read for Fri., 11/19: Sect. 8.2 (all).

Do for discussion on:
Fri. 11/19: Ch. 8, ## 11, 12(a,b,c), 17, 19(a).
Mon. 11/22: Any problems or questions you want to review, and Ch. 8, ## 12(d), 19(b).

TEST II is on Tuesday, Nov. 23. It will cover Homework Sets VII-XII.

HOMEWORK SET XIII (11/28)

Read for Mon. 11/29: Section 3.1.

Do for discussion on
Tues. 11/30: Ch. 3, ## 1, 4, 5, 7.
Wed. 12/1: Ch. 3, ## 2, 3, 9, 16 (see remark), 18, 26.

Hand in Fri. 12/3:
Ch. 3, ## 1 (for k = 23, 24), 6, 11, 15, and # H4.

HOMEWORK SET XIV (11/28)

Read for Mon., 12/6: Section 3.2.

Do for discussion on:
Tues. 12/7: Ch. 3, ## 8, 13, 14, 19(a), and ## H1, H2(a,b), H3(a,b).

Hand in Wed. 12/8: Ch. 3, ## 17, 19(b,c), and ## H1, H2(c), H3(c).

Problem Set H

Problem H5 is not assigned. It's for anyone whose curiosity was tickled by Problem 3.19.

H1. In Ch. 3, # 1, how high can you push k, the number of games? (This is a challenging problem, but it is answerable with the knowledge we have.)
H2. 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.
H3. 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, -π, π, 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.
H4. This concerns Ch. 3, #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?
H5. * Here's a challenge for anyone who wants to know if the answer n² + 1 is the best one to Problem 3.19. Can you find n² points in the unit equilateral triangle, so that every pair has distance > 1/n? This problem has to be approached carefully because the behavior changes as n gets larger. Start with n = 1, 2, 3, and see what happens. Then think about n = 4, then n = 5, and maybe bigger values.