CSci 271 Lecture Notes
Week Seven, Wednesday: Basics of Counting and Pigeonhole Principle
Basic Counting Principles
The sum rule.
The product rule.
The Inclusion-Exclusion Principle
Overlapping sets: cardinality of the union.
Tree Diagrams
Playoff outcomes.
Pigeonhole Principle
If the number of items to assign is greater than the number of slots to
assign them to, then some slot will be assigned more than one item.
Generalized Pigeonhole Principle
Generalize the pigeonhole principle for multiples of slot set cardinality.
Some Elegant Applications of the Pigeonhole Principle
Theorem 3: increasing/decreasing subsequence length.
Homework Assignment
Assigned Wednesday, October 21, due Wednesday, October 28, at beginning of class.
Chapter 3.1: 2, 10.
Chapter 3.2: 5, 6.
Chapter 3.3: 2, 24.
Chapter 4.1: 2, 6.
Chapter 4.2: 6, 14.
This page established October 21, 1998; last updated October 23, 1998.