Math 112 (Introductory Discrete Mathematics), spring semester, 2004/5

Instructors:

Ayşe Berkman, Mahmut Kuzucuoğlu and David Pierce

Catalogue description:

Basic counting: The sum and product rules, the pigeonhole principle, generalized permutations and combinations. The binomial theorem. Discrete probability. Inclusion-Exclusion. Recurrence relations. Introduction to graphs and trees.

Detailed description:

We aim to answer the following sorts of questions, many of which we shall express in terms of physical situations, not just abstractly as here:

• How many ways can k objects be selected from a set of n objects? (The answer depends on whether the selection is ordered, and on whether objects can be repeated.)
• In a sequence a₀, a₁, a₂, a₃, …, if each member a_k+2 is determined by a_k and a_k+1, can we compute a_n directly?
• Can you walk around a given graph, using exactly once each edge?—each vertex?
• Can you draw a given graph in a plane, with no crossing edges?
• What sorts of geometrical solids exist with certain symmetrical features?
• How many ways can n different objects be sorted into several bins of given sizes?
• How does the size of a union of sets depend on the sizes of the individual sets?

Concerning probability, we introduce the notions of random experiment, sample space, outcome, and event, along with a measure that assigns a probability to each event. Probabilities respect a version of the Inclusion-Exclusion Principle. There are notions of conditional probability and independent events. A Bernoulli process consists of Bernoulli trials: identical but independent random experiments with just two outcomes each.

Our main goal is to recognize and work with common themes in various physical situations involving numbers (or objects repeated finitely many times).

References:

• Ian Anderson, A First Course in Discrete Mathematics (London: Springer, 2001), chapters:
  1. Counting and Binomial Coefficients;
  2. Recurrence;
  3. Introduction to Graphs;
  4. Travelling Round a Graph;
  5. Partitions and Colorings;
  6. The Inclusion-Exclusion Principle
• Paul Dierker and William L. Voxman, Discrete Mathematics, ch. 9: Elementary Probability Theory
• Discrete mathematics problems: these include some problems from earlier exams.

Examinations:

1. March 22 (Tuesday, 17.40), on ch. 1, sections 1–5, and ch. 2, sections 1, 2 and 4.
2. April 26 (Tuesday), on §§3.1–3, 3.5–7, 4.1, 4.2, 4.5
3. Final exam (on the subjects covered in the in-term exams, along with: counting partitions of a set; the Inclusion-Exclusion Principle; and probability)
4. Make-up exam (for those who have made arrangements with their teachers): June 13 (Monday, 9.30), in M-104.

Solutions

Web-pages from some previous years:

• 2001/2
• 2002/3