Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAPTER 5 Techniques of Counting

5.1Introduction

This chapter develops some techniques for determining, without direct enumeration, the number of possible
outcomes of a particular event or the number of elements in a set. Such sophisticated counting is sometimes
calledcombinatorial analysis. It includes the study of permutations and combinations.

5.2Basic Counting Principles

There are two basic counting principles used throughout this chapter. The first one involves addition and the
second one multiplication.

Sum Rule Principle:

Suppose some eventEcan occur inmways and a second eventFcan occur innways, and suppose both

events cannot occur simultaneously. ThenEorFcan occur inm+nways.

Product Rule Principle:

Suppose there is an eventEwhich can occur inmways and, independent of this event, there is a second event

Fwhich can occur innways. Then combinations ofEandFcan occur inmnways.

The above principles can be extended to three or more events. That is, suppose an eventE 1 can occur inn 1
ways, a second eventE 2 can occur inn 2 ways, and, followingE 2 ; a third eventE 3 can occur inn 3 ways, and so
on. Then:

Sum Rule: If no two events can occur at the same time, then one of the events can occur in:

n 1 +n 2 +n 3 +···ways.

Product Rule: If the events occur one after the other, then all the events can occur in the order indicated in:

n 1 ·n 2 ·n 3 ·...ways.

88

Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.