Combinatorics and computing

Figure 9.2



Solution Since there is no doubling back, a journey from A to B consists of a list of segments, where each segment is the length of a single block, either south (S) or east (E). For example, one such journey is ESSEEESESEEE. There must be 8 segments east and 4 segments south, and these 12 segments can be arranged in any order. The problem then becomes: in how many different ways can 8 Es and 4 Ss be arranged?
This can actually be treated as a combinations problem, although at first sight it might not appear to be one. The number of such arrangements is just the number of different ways of selecting the positions of the 4 Ss from the 12 available positions in the list. (Once the positions of the Ss have been chosen, the Es must occupy all the other positions.) The answer is:

There are 495 different journeys.
The binomial coefficients satisfy a number of identities. One of the most useful of these is the following identity:

This result is easily proved by writing out each side in terms of factorials. It is useful in computations, because it allows a binomial coefficient with r > n / 2 to be replaced by one with r < n / 2.
For example, rather than evaluate directly, it is simpler to replace it with ( 30 ) using the identity above:

Some other useful identities are:

The first two identities follow immediately from the definition of (remembering that 0! = 1). You are asked to prove the third identity in the exercises.
The third identity forms the basis of a simple method for generating and displaying the binomial coefficients row by row. The top row of the display contains just the number 1, which is the value of . Beneath it are the values of and , the binomial coefficients corresponding to n = 1. The next row contains the values of and , the binomial coefficients corresponding to n = 2, and so on. The first and last entries in each row are 1, because . Each other entry is obtained by adding the two numbers immediately above it, because The first six rows (corresponding to values of n from 0 to 5) are shown below:

This way of displaying the binomial coefficients is called Pascal’s triangle, after the French mathematician Blaise Pascal (1623 – 1662) who investigated its properties, although it was known to earlier mathematicians.