CS 494/MATH 450: Applied Combinatorics

Kalamazoo College

Spring 2004

Readings & Assignments

Reading Assignments, Projects and Presentations will be listed here in chronological order, i.e., with the most recent ones at the bottom of the list.

All reading assignments are from the textbook, Applied Combinatorics by Roberts, unless specified otherwise.

This document was last modified on June 3, 2004.

Date assigned Reading
(to discuss next time)		 Problems to try
(for next time)		 Problems to hand in
(Well written)		 Due Date
(for hand-in problems)
March 30
 Chapter 1, Sections 2.1 - 2.6 Chapter 1: 3, 4, 5, 12a, 12b
2.1: 1, 8, 9
2.2: 2, 5
2.3: 2, 6
2.4: 2, 6
2.5: 2, 5
2.6: 3, 5
 Chapter 1: 6, 12c, 12d
2.1: 2, 12
2.2: 4, 6
2.3: 3, 7
2.4: 4, 5
2.5: 3, 4
2.6: 2, 4, 6
 April 6
April 1
 2.7 - 2.9 Think about the birthday problem: Start with an arbitrary person. What is the probability that the second person's birthday is different? What is the probability that the third person's birthday is different from the first two? (ie, second is different from first and third is different from second) Continue through the nth person. Then what is the probability that at least 2 people have same birthday? How big does the group n have to be in order to have a 50% chance that two people have the same birthday?
2.7: 8, 11, 15
2.8: 8
2.9: 1, 3, 7, 9, 14		 2.7: 10, 13, 17
2.9: 5, 10, 13
Additional Problem: The Prime Number Theorem tells us that the number of primes not exceeding the real number x is about x/log(x). What is the probability that a number near x is prime? 		April 6
April 6
 2.10 - 2.12 2.10: 5, 6
2.11: 3, 4, 5, 6, 16
Classify the following problems according to whether or not the "balls" and "cells" are distinguishable, and whether or not we can have empty cells. Think about how you might solve them.
  • How many ways are there to distribute 40 identical jelly beans among 4 children without restrictions? With each child getting 10 beans? With each child getting at least 1 bean?
  • How many ways are there to distribute 4 identical oranges and 6 distinct apples (each a different variety) into five distinct boxes? In what fraction of these distributions does each box get exactly two objects?
  • How many ways are there to distribute 20 cents to n children and one parent if the parent receives either a nickel or a dime, and the children receive any amounts? Each child receives at least 1 cent? Each child receives at most 1 cent?
April 9
 2.12 - 2.15, 2.17 2.11: 20, 22
2.12: 1, 5, 8, 14
2.14: 1, 7 		See Homework 2 April 20
April 15
 3.1.1, 3.1.2, 3.2, 3.3.1, 3.3.3, 3.4.1, 3.4.2, 3.5.1, 3.5.2, 3.5.4, 3.5.5, 3.5.6 3.1: 7, 9, 10
3.2: 1, 5, 6
3.3: 3, 4, 5
3.4: 1, 2, 3
3.5: 3, 7, 10, 18
April 20
 4.1, 4.2 Finish problems from 3.3 and 3.4 above
4.1: 3a, b, c, i, l, 4a, d, h, 11
4.2: 1a, f, 2a, b, 4a, b, 6
April 22
 4.3, 4.4 Use generating functions to compute the first and third supplemental problems from April 6.
4.3: 1a, c, d, g, h, l, 6
4.4: 3, 6, 8, 19		 Homework 3 April 29
April 27
 4.5 4.5: 1b, c, 2a, f, 6a, d, h, 12
May 6
 5.1, 5.2 5.1: 12, 14, 18, 23, 25
5.2: 1, 2, 10, 11a, e, j, 23a, b, 24a, b		 Homework 4 May 13 - extended to 4PM May 14
May 13
 5.3, 5.4.1, 5.4.2 (review 4.4 if necessary)
May 18
 6.1.1 - 6.1.4, 6.1.7, 6.1.8, 6.2.1
May 20
 8.1, 9.1, 9.2 Homework 5 May 27
May 27
 10.1 -10.3, 10.4 (Just as far as examples 10.4 and 10.5)
June 3
 13.3.1 - 13.3.5