COT 3100 Sect. #7094X (Fall 1999)
Homework Assignment #7:
Combinatorics
Assigned Wed. 10/20/99, due at the start of class Wed. 10/27/99

All problems are taken from the textbook (Rosen), §4.1 - 4.3. You should also practice the odd-numbered problems in those sections, whose solutions you can check in the back of the book, or review in more detail in the student solutions guide. Practicing other even-numbered problems may also help you. Each assigned book exercise is worth 1 point out of a total of 17.

We are still using the same optional collaborative homework policy that we used in the previous assignments. (Group work is permitted, if you turn in a joint assignment.)

Unless otherwise indicated, the listed extra credit exercises are each worth 1 extra points out of the 17, up to a maximum score of 100%.

Exercises from §4.1, pp. 242-244. (The Basics of Counting)

• Ex. 6 - Count total number possible routes.
• Ex. 14 - Count the number of bit-strings satisfying a certain condition.
• Ex. 20 - Count the number of integers satisfying certain conditions.
• Ex. 24 - Count the number unique licence plate numbers.
• Ex. 38 - Count number of ways of doing something and satisfying conditions.
• Ex. 42 - Apply counting rules
  Extra credit:
• Ex. 52 - Using product rule to prove something

Exercises from §4.2, pp. 248-250. (The Pigeonhole Principle)

• Ex. 6, 10, 16, 22, 34 - Various proofs using the Pigeonhole principle.
  Extra credit:
• Ex. 30 - Another proof.

Exercises from §4.3, pp. 257-260. (Permutations and Combinations)

• Ex. 6 - Find the values of the quantities given.
• Ex. 16 - Count number of bit-strings satisfying certain conditions.
• Ex. 18 - Count number of ways.
• Ex. 20 - Count number of possible unique answers.
• Ex. 33 - A proof.
• Ex. 40 - Binomial Expansion
  Extra credit:
• Ex. 42 - Find a general formula for the kth expansion term.