The Basic Rules of Counting

The Inclusion-Exclusion and the Pigeonhole Principles are the most fundamental combinatorial techniques. There are two additional rules which are basic to most elementary counting. One is known as the Sum Rule (or Disjunctive Rule), the other is called Product Rule (or Sequential Rule.)

Below, |S| will denote the number of elements in a finite (or empty) set S. So, for example, |{}| = 0 and |{0}| = 1. The empty set {} is denoted Ø.

Comment: behind the set-theoretic symbolism stands a simple fact without which counting would be impossible: it does not matter how you count, i.e., as long as you do not make a mistake of, say, missing an object or counting an object twice. It says this: if before counting objects one splits them into two groups and then counts the elements of one of the groups before proceeding to count the elements of the other, the result will be the same - the total number of objects to be counted. (Naturally, it does not depend on how the objects have been split into two groups.)

Example 1

In a class of 30 students, there are 16 boys and 14 girls (16 + 14 = 30). Of these, 23 persons wear pants and only 7 wear skirts (23 + 7 = 30). On the last exam 20 students received a passing grade, while 10 failed (20 + 10 = 30).

By induction, the sum rule is easily extended to any finite number of mutually disjoint sets:

Example 2

An electronic book of 472 pages has been stored in separate files - 1 file per page - in two folders. One folder contained 305 files, the other 167 files (305 + 167 = 472.)

For a direct product A×B of two finite sets A and B,

Comment: By induction the rule extends to any finite number of sets:

An essential point here is how the tuples of objects are formed: an object is picked out from one of the given sets regardless of which objects have been drawn from the other sets. Why the rule is called sequential? Because in a tuple, the objects (components) are ordered: there is the first one, the second, and so on.

Example 3

The are two drawers. One contains 12 shirts, the other 7 neckties. There are 84 = 12×7 ways to combine a shirt and a necktie.

It is possible to examine the drawers sequentially: first-second, first-second... It is also possible to form combinations using two hands: left for a shirt, right for a necktie. As long as all possible combinations shirt/necktie have been counted, the exact procedure is of no consequence.

Example 4

A test consists of 6 mutiple-choice questions. Each question has 4 possible answers. There are

ways to answer all 6 questions.

Counting poker hands provides multiple additional examples.

References

1. V. K. Balakrishnan, Theory and Probl ems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995
2. S. B. Maurer and A. Ralston, Discrete Algorithmic Mathematics, A K Peters, 3^rd edition, 2004.

|Contact| |Front page| |Contents| |Algebra| |Store|