Combinatorics and computing

Chapter 9 Combinatorics

9.1 Combinatorics and computing
Combinatorics is the branch of mathematics devoted to calculating the number of ways in which a specified process can be carried out. Problems of this type often occur in computing. A typical problem is to determine how many times a particular sequence of steps in an algorithm will be executed. You might need to know this in order to estimate how long the algorithm will take to run. For example, a simple algorithm for determining the shortest path for a signal to travel through a communications network might begin by calculating the lengths of all of the possible paths through the network. A better algorithm might arrive at the correct answer after calculating just the lengths of a selection of paths. In order to determine how efficient these algorithms are, and to be able to compare them with each other and with other algorithms, we must first answer the question: ‘How many such paths are there altogether?’
In this chapter, we present some basic counting techniques that can be
used to solve problems of this type.