Binghamton University

Links to Homework Sets: Set I | Set II | Set III | Set IV | Set V | Set VI | Set VII | Set VIII | Set IX | Set X | Set XI | Set XII | Set XIII | Set XIV

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

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.

- 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
^{2}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^{2}. Suppose you have a relaxed magic square of order n. Then replace each number a_{ij}in the square by n^{2}- a_{ij}. Do you still have a relaxed magic square?]

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.

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

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

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

- B1. Prove combinatorially the formula in Ch. 5, #19:
m
^{2}= 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?

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

- C1. Evaluate (that means, as an actual number) the following binomial coefficients. Look for patterns. Simplify.
- (5 choose 4), (4 choose 5), (5.6 choose 2).
- (0 choose 0), (0 choose 7).
- (7 choose −1), (0 choose −1).
- (−1 choose r) for r = 0, 1, 2, 3. Can you guess a general pattern for (−1 choose r) (no proof required)?
- (−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).

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

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

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

- E1. Find the number of solutions to x
_{1}+ x_{2}+ x_{3}+ x_{4}= 22 in integers that satisfy

x_{1}≤ 14, x_{2}≤ 14, x_{3}≤ 14, x_{4}≤ 7, and- all x
_{i}≥ 0; - all x
_{i}> 0.

- all x
- E2. Find a formula for the number of r-combinations of the multiset

M = {infty·a_{1}, infty·a_{2}, 100·a_{3}, 100·a_{4}},

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

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

- 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.- m = 3,
- m = 4,
- m = 5,
- m = 6,
- * 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.

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

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

- G1. Calculate the Catalan numbers C
_{11}and C_{12}using formulas and data in Section 8.1. - G2. In a multiplication scheme for a
_{1}, a_{2}, ..., 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_{1}(( a_{2}a_{3}) ( a_{4}a_{5}))) a_{6}).

(b) (( a_{3}(( a_{2}a_{5}) ( a_{4}a_{6}))) a_{1}). - 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
_{1}, a_{2}, ..., a_{n}, taken in that order, and the acceptable sequences of n-1 +1's and n-1 -1's.

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

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

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

- 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
- n = 3, N = 9;
- n = 4, N = 16;
- N = n
^{2}for any n ≥ 1.

- H3. Concerning Application 9, here are some sequences of N = n
^{2}+ 1 numbers. For each sequence, find m_{1}, m_{2}, ..., 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.- n = 3, and the sequence is 3, -1, -π, π, 3.2, 1.88, 3, 0, 14, 7.
- n = 3, and the sequence is 5, 9, -2, 0, -1, -4, 55, 44, 22, 23.
- n = 3, and the sequence is 5, 9, -2, 55, -1, -4, 0, 44, 22, 23.

- H4. This concerns Ch. 3, #9.
- Prove the same conclusion is true if there are 9 people in the room.
- Prove that the conclusion does
*not*necessarily follow if the number of people in the room is 6. - 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
^{2}+ 1 is the best one to Problem 3.19. Can you find n^{2}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.

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