Counting

Introduction to Counting

The problem of how to count things arises very often not only in computer science and mathematics but also in our everyday life. (How many different routes exist from one's house to one's office ?) How many different ways exist to fly from Norfolk, VA to San Francisco ? How many different ways of combining skirts and blouses (or pants and jackets) you have exist ? How many different codes can be constructed with a given number of bits ? How many operations are used by an algorithm in the worst case ? on the average ? --- estimate of computation time How many different types of shirts can be made if they can be any of 12 colors, either of male or female version, and any of three sizes for either sex ? During some 30 day month a baseball team plays at least one game a day, but no more than 45 games. Then there is a stretch in that month during which the team must play exactly 14 games. True or false ? These are just a few of the examples of the so called couning problem. This seemingly trivial problem is in general not trivial and in some cases quite clever ideas are needed to solve it. In this chapter we study some of the basic techniques of counting. The next section presents two basic principles of counting, then the following section discusses a little more more advanced topics of inclusion-exclusion principle and the pigeon hole principle. Permutations and combinations are not covered here because they are usually covered in a probability and statistics course.


Next -- Basic Principles of Counting

Back to Schedule
Back to Table of Contents