Advanced Mathematics

2.3Counting: The Art of Enumeration

Purpose of Section

To introduce some basic tools of counting the members of a set, and to do this, we introduce a variety of tools of the trade, such as the multiplication principle, permutations, and combinations. We show how the multiplication rule gives rise to counting permutations and combinations. We close with a brief introduction to the pigeonhole principle, and show how such a ridiculously simple idea can solve some ridiculous difficult problems.

2.3.1 Introduction

Although counting is one of the first things we learn at a tender age, be assured there are counting problems that test the mental agility of the brightest minds among us. In this section, we will learn to count, although we refer to it as combinatorics. We will answer such counting questions as

how many ways can 10 people choose sides and play a game 5 against 5?

Counting problems often require almost no technical background and are often characterized by being easy to understand and hard to solve. Finding the number of ways to cover an 8 x 8 checkerboard with dominoes is a good example. The problem is easy to understand, but the number of coverings was not determined until 1961 by a M. E. Fischer, who found the number to be 2⁴ × (901)² = 12 988 816.

To assist you in perfecting counting skills, we introduce one of the basic tools of the trade, the multiplication principle.

2.3.2 Multiplication Principle

One of the basic principles of counting is the multiplication ...