4.1 Introduction

You have already had several occasions in this book to count things. Indeed, number is one of humanity s fundamental concepts, and counting is one of the fundamental intellectual urges. Ever tried to count the stars in the sky or just the students in your math class? Ever wondered how many matching outfits you could put together from your wardrobe?

We will concentrate in this chapter on how to count without worrying too much about what we count. We realize that this approach can be taken to an unfortunate extreme. Who cares how many ways a baseball manager can order nine players to form a lineup, or an anagrammist can rearrange the letters of Mississippi ? The manager would never consider all possible lineups to be equally worthy, and the anagrammist would never need to know how many ways the reordering could take place.

However, there is something to say for doing such toy examples. First, they are easy to state clearly and quickly, and so we can get on with the main business of learning solution methods. Second, they remind us that, in many situations where there is a lot of choice, the real issue is to find an optimal solution. Often the first step in solving optimization problems is to get an idea of how many choices there are. In an age of computers, if the number is not too large, brute force may be an effective algorithm find the best choice by trying them all. Even...