Math 386: Combinatorics Homework Assignments

Due Thurs. 8/31:

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

HOMEWORK II

Due Fri. 9/1:

Hand in Thurs. 9/7: Ch. 1, ## 13, 16, 25, 27

HOMEWORK III

Read Sects. 3.1-3.3.
Do for discussion on

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

HOMEWORK IV

Read Sects. 3.4-3.5.
Do for discussion on

Hand in Fri. 9/22: 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

Hand in Fri. 9/29: ## 6,8, 9, 11, 14, 18, and B2.

HOMEWORK Va

Read Sects. 5.1, 5.2, and 5.3 (complete).
Do for discussion on

Hand in Fri. 10/6: ## 6, 8, 9, 11, 13, 14 (as stated), 18, and B2.

HOMEWORK VI

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

Hand in Mon. 10/16: ## 20, 24, 32, and C3.

Problem Set B

• B1. Prove combinatorially the formula in Ch. 5, #19: m² = 2 C(m, 2) + C(m, 1).
• B2. Give a combinatorial proof of Chapter 5, #13.

Problem Set C

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

HOMEWORK VII

Read Sections 6.1-6.2.
Do for discussion on

Hand in Fri. 10/20: Ch. 6, ## 2, 5, and ## D2, D3.

Problem Set D

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

  D2. Find the number of solutions to x₁ + x₂ + x₃ + x₄ = 22 in integers that satisfy x₁ <= 14, x₂ <= 8, x₃ <= 15, x₄ <= 7, and

  (a) all x_i >= 0;

  (b) all x_i > 0.

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

HOMEWORK VIII

Read Section 6.3.
Do for discussion on

HOMEWORK IX

Read Sections 6.4-6.5.
Do for discussion on

Hand in Fri. 11/3: Ch. 6, ## 13, 14, 24(b), 26, 28, 30.

Problem Set E

• E1. Let t be a positive integer and let M be the multiset {t·a₁ , t·a₂ , ..., t·a_k}. 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.

Do for discussion on:

Hand in Fri. 11/10: Ch. 2, ## 3, 6, 11, 17, 19.

Problem Set F

• F1.(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?

  F2.Find the number of permutations of S_n = {1,2,...,n} subject to the restrictions: no integer is immediately followed by its successor (that's the next higher integer), no odd integer is immediately followed by the next higher odd integer, and:

  (a) n=3,

  (b) n=5,

  (c) n=7,

  (d) any n.

HOMEWORK SET XI (2000/11/1)

Read Section 2.2. (See correction.)

Do for discussion on:

Problem Set G

Handouts, nicely printed, are available on my office door (as of Sunday morning).


• G1. By X_n 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. In class we showed that X_n is true for n <= 102 by using the basic PHP argument, but this argument didn't work for larger n.
  (a) Decide whether X₁₀₃ is true or false, if you can.
  (b) Find a value of n (it will be large) for which X_n 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.
  
  

  G2. Consider the set Z₃₂ = {0, ..., 31}. In the codebook of spy ``X'', some of the numbers in Z<sub>32</sub> 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 Z<sub>32</sub> 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 Z₃₂): 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 Z₃₂ 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.
  
  

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

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

  G4. Find a sequence of N numbers that has no increasing and no decreasing subsequence of length n + 1, where

  (a) n = 4, N = 9;

  (b) n = 5, N = 16,

  (c) N = n² for any n >= 1.
  
  

  G5. In connection with Application 4, k = 23, we took care of the case in which the missing number is 23. Solve the cases in which the missing number is other than 23.
  
  

  G6. In connection with Application 4, solve as many values of k > 23 as you can.

HOMEWORK SET XII (11/17)

Read Section 2.3, except the material on t-element subsets on pages 40-41.

Do for discussion on:

HOMEWORK SET XIII (11/27)

Read Section 5.6, pp. 147-8, and Section 7.1.

Do for discussion on:

Hand in Fri. 12/1: Ch. 7, ## 1(d), 3(d), 7.

Problem Set H

• H1. For use in the binomial series, ``evaluate'' (or ``simplify'') the binomial coefficients (r choose n) 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.)
• H2. Substitute your answers from H1 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 XIV (and last) (11/27)

Read Sections 7.4-5.

Do for discussion on:

Hand in Thurs. 12/7: ## 23(e), 24(e), 25(d), 30