Chapter 7

COUNTING

7.1 A PARTY PROBLEM

It is always necessary to count how many ways certain choices can be made. In computer science, we may have to estimate the number of times a certain procedure is called during the execution of a program, in order to assess a program’s efficiency. In this section, we present some of the basic methods for counting the number of ways in which events can occur.

Let us consider that Mala has invited six friends to her birthday party. When they arrive, they shake hands with each other. The common question posed by all participants is “How many handshakes does this mean?”

One friend of Mala says that, “I shook 6 hands altogether.” Whereas another friend gave the opinion saying, “Since there are seven of us, this ...

Get Discrete Mathematics now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.