Numbers that arise of their own accord in counting problems are important and so have been extensively investigated. Here I will describe the binomial coefficients, and the numbers of Catalan,Fibonacci, and Stirling because they enumerate certain natural collections. But we first begin with some very fundamental number sequences.

Triangular numbers, arithmetic and geometric progressions

Since they will reappear when we look at binomial coefficients,I will take a moment to revisit the triangular numbers, the nth of which, denoted by tn, is defined as the sum of the first n counting numbers. Its value, in terms ofn, can be found by the following trick. We write tn as the sumjust mentioned and then again as the same sum but in the reverse order. Adding the two versions of tntogether:

tn=1+2+3+…+(n-2)+(n-1)+n

tn=n+(n-1)+(n-2)+…+3+2+1;

For example, by taking a=1 and b=2, we see that the sum of the first nodd numbers is n+n(n-1)=n+n2-n=n2, the nth square.

If we replace addition by multiplication as the operation, we move from arithmetic series to geometric series. In an arithmetic series,each pair of successive terms is separated by a common difference,the number b in our notation. In other words, to move from one term to the next, we simply add b. In a geometric series, we once again begin with some arbitrary number, a as the first term and move from one term to the next by multiplyingby afixed number,called the common ratio, denoted by the symbolr. That is to say,the typical geometric series has the form a, ar, ar2,…with the nth term being arn-1. As with arithmetic series, there is a formula for the sum of the first nterms of a geometric series:

The quick way of seeing that this formula is right is to　 take the equivalent form that we obtain when we multiply both sides of this equation by(r-1)and multiply out the brackets. On the left-hand side we obtain:

(ar+ar2+ar3+…+arn)-(a+ar+ar2+…+arn-1)

and the whole expression telescopes, meaning that nearly every term is cancelled by one in the other bracket:the only exceptions are arn-a=a(rn-1), showing that our formula for the sum is correct. For example, putting a=1 and r=2 gives us the sum of powers of 2:

1+2+4+…+2n-1=2n-1.

This formula isjust what you need in order to verify Euclid’s result from Chapter 3 on howto generate even perfect numbers from Mersenne primes.

Factorials, permutations, and binomial coefficients

As we have seen, the nth triangular number arises from summing all the numbers from 1 up to ntogether. Ifwe replace addition by multiplication in this idea, we get what are known as the factorial numbers, which made their first appearance in Chapter 2.

Factorials come up constantly in counting and probability problems such as the chances of being dealt a certain type of hand in a card game like poker. For that reason, they have their own notation:the nth factorial is denoted by n!=n×(n-1)×…×2×1. Thetriangularnumbers grow reasonably quickly, at about halfthe rate of the squares, but the factorials grow much faster and soon pass into the millions and millions:for example 10!=3,628,800. The exclamation mark alerts us to this rather alarming rate of growth.

The most special class that emerges in counting problems, or enumerations as they are called, is that of the binomial coefcients,so named as they arise as the multipliers of powers of x when the binomial expression(1+x)n is expanded. The binomial coefcient C(n，r)is the number of different ways we may construct a set of size r from one of size n. For example, C(4，2)=6, as there are six pairs(taken without regard to order within a pair)that can be chosen from a group of four:for example, if we have four children,Alex, Barbara, Caroline, and David, there are six ways that we can select a pair from this group:AB, AC, AD, BC, BD, and CD.

The binomial coefcients can be calculated in two distinct ways.First, we can extend the argument above that we used to calculate C(52，5):in general we see that C(n，r)=P(n，r)r!, which in turns gives us the useful expression:

A notable special case is when we let r=2, which corresponds

to the number of pairs that can be selected from a set of n objects.

This factorial-based formula for calculating binomial coefficients does give a nice algebraic hold on the binomial coefficients that allows us to demonstrate their many special properties. However,the evolution of these properties is often more transparent ifwe focus on a second way to generate these integers, which is by means of theArithmetic Triangle(see Figure 2), also known as Pascal's Triangle, in honour of the 17th-century French mathematician and philosopher Blaise Pascal(1623–62).(The Arithmetic Triangle has been discovered and re-discovered throughout Persia, India, and China over the last 1,000 years:for example, it featured as the front cover of The Precious Mirror by Chu Shih-Chieh in 1303.)

2. The Arithmetic Triangle

Each number in the body of the triangle is the sum of the two above it. The triangle, which can be continued indefinitely, gives the full list ofbinomial coefficients. For example, to find the number ofways ofselecting five people from a group ofseven,proceed as follows. Number the lines of the triangle, beginning with 0 at the top. Similarly number the positions within each row from left to right, again starting with 0. Go down to the line numbered 7, and then go to the number on thatline numbered 5(remembering to start your count from 0):we see the answer is 21.You will note the symmetry ofeach row:for example,21 is also the number ofways ofchoosing two people from a group ofseven.This is explained by observing that when we choose the five from seven, we are simultaneously choosing two from seven as well–the two being the pair left behind. This symmetry argument of course applies to every row. This is also manifested in the formula on page 55, for it returns the same expression ifwe replace r by n-r, as the terms r and n-r that we see in the denominator simply swap positions.

The reason that the pattern gives the right answers is not hard to see. Each row builds from the one above it. We can see easily that the first three rows are correct:for example, the 2 in the centre of the third row tells us that there are two ways ofchoosing a single person from a pair. The 1 that sits on top is saying that there is one way to choose a set ofsize zero from the empty set. In fact, there is one way ofchoosing a set ofsize zero from any set,which is why every row begins with 1. Let us focus on the example just given–there are 21=15+6 ways ofselecting five from a group ofseven people. The 21 quintets naturally split into two types. First, there are 15 ways to form a group offour from the first six people, to which we may add the seventh person to form our fivesome. Ifwe don’t include the seventh person, however, then we have to build a set of five from the first six, and there are six ways ofdoing this. This illustrates how one row leads to the next:each entry is the sum of the two above it, and this pattern propagates throughout the triangle. In symbols this rule takes the form:

C(n, r)=C(n-1, r)+C(n-1, r-1).

The triangle is rich in patterns. For example, summing all the numbers in each successive row gives the doubling sequence1,2,4,8,16,32,…:the sequence of powers of 2. In summing the row that begins 1,8,28,56,…for instance, we are summing the number of ways of choosing a set of size 0,1,2,3 etc. from a set of8. In total, this gives us the number of ways of selecting a set of any size from a group of 8, which is equal to 28 as, in general, a set of size n contains 2n subsets within it.

This last fact can be seen directly, for a subset of a set of size n can be identified by a binary string of length nin the following way. We consider the set in question in a specific order{a1, a2,…, an}say,and then a binary string of length n specifies a subset by saying that each instance of 1 in the string indicates the presence of the corresponding ai in the subset in question. For example, ifn=4,the strings 0111 and 0000 stand respectively for{a2, a3, a4}, and for the empty set. Since there are two choices for each entry in the binary string, there are 2n such strings in all and therefore 2nsubsets within a set of size n.

Catalan numbers

One of the simplest visual representations that gives rise to this number type is as the number of ways we can draw‘mountains’using n up strokes and n down strokes(see Figure 3)

3. Withthree up and down strokes there are five mountain patterns

Each mountain pattern has an interpretation, however, as a meaningful bracketing and so the number of meaningful ways of arranging a collection of n pairs of parentheses is the nth Catalan number. For example,(())()and((()))are meaningful bracketings but())(()is not:to be meaningful, the number of left brackets must never fall behind the number of right brackets as we count from left to right. This corresponds to the natural condition that our mountains must never dive underground. For instance, the first and last mountain patterns in Figure 3 correspond to the bracketing()(())and()()()respectively.

The nth Catalan number also counts the number of ways that we can break up a regular polygon with n+2 sides into triangles by means of diagonals that do not cross one another, and there are other interpretations along these lines. As with binomial coefficients, there are formulas relating Catalan numbers to smaller Catalan numbers, which makes them amenable to manipulation.

Fibonacci numbers

The Fibonacci sequence is one series of numbers that engenders wide fascination among the general public. The sequence runs as follows

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,…

where each number after the pair of initial 1s is the sum of the two that come before. In this, there is a similaritywith the binomial coefficients in that each term is the sum of two previous ones in the sequence, but the method of formation of the Fibonacci numbers is simpler:

fn=fn-1+fn-2

where fn denotes the nth Fibonacci number and we fix f1=f2=1.We call such a formulathat defines each member of a sequence in terms of its predecessors a recursion or a recurrence relation.

How does this sequence arise? It was first introduced in 1202 by Leonardo of Pisa, better known as Fibonacci, in the form of his celebrated Rabbit Problem. A female rabbit is born and after two months reaches maturity and thereafter gives birth to a daughter each month. The number of female rabbits we have at the beginning of each month is then given by the Fibonacci numbers,for there is 1 rabbit at the beginning of the first month, and the second, but at the start of the third month she gives birth to a daughter so we then have 2 rabbits. Next month she has another,giving 3 and the month after that we have 5 bunnies as both mother and her eldest daughter are now old enough to breed. In general, at the beginning of each month thereafter, the number of newborn daughters equals the number of females we had two months ago, as only they are old enough to breed. It follows that the number of females we have at the start of each subsequent month equals the total of the previous month(Fibonacciís rabbits are immortal)plus the number we had the month before that.Therefore the rule of formation of the Fibonacci numbers exactly matches the breeding pattern of his rabbits.

Despite the fact that real rabbits do not breed in this contrived fashion, Fibonacci numbers arise in nature in a variety of ways,including plant growth. The reasons for this are well understood but are related to more subtle attributes of the sequence connected to the so-called Golden Ratio, a number that we are about to introduce.

The simplest types of number progressions are the arithmetic and geometric progressions introduced in the first section. Although the Fibonacci sequence is neither of these, it does however have a surprising link with the latter type. Ifwe form the sequence of differences of the Fibonacci sequence, because of the way the sequence is defined, we get 0,1,1,2,3,5,8,13,…, that is we recover the Fibonacci sequence again except this time beginning at 0. This happens precisely because of the way the sequence is formed:the difference of two consecutive Fibonacci numbers is the one immediately preceding both in the sequence.(To see this algebraically, subtract fn-1 from both sides of the Fibonacci recurrence above.)Nor is the sequence a geometric progression as the ratio of consecutive Fibonacci numbers is not constant. All the same, when we look at the ratio of successive terms we see that it does seem to settle down to a limiting value. This near stable behaviour of the ratio comes about quite quickly, as we see as we divide each Fibonacci number by its predecessor:

But what is the mysterious number,1.6180..., which we see emerging? This number τ is known as the Golden Ratio, and it arises quite of its own accord in geometrical settings that look a world away from Fibonacci’s rabbits. For example,τ is the ratio of the diagonal of a regular pentagon to its side(see Figure 4). Each diagonal meets another at a point that divides each into two parts that are themselves in the ratio τ:1. Pairs of intersecting sides and intersecting diagonals form the four sides of a rhombus(a‘square’parallelogram)ABCD as shown. Where diagonals cross, they form a smaller inverted pentagon.

4. Pentagon andthe Golden Rectangle

Another way ofretrieving this valuation of τ is through its so-called continued fraction, which ties τ directly to the Fibonacci numbers, and we shall explore this idea in Chapter 7.

In the long run, the Fibonacci sequence behaves like a geometric progression based on the Golden Ratio. It is this property,together with its simple rule of formation that causes the Fibonacci sequence to arise so persistently.

Stirling and Bell numbers

Like the binomial coefficients, the Stirling numbers often arise in counting problems and depend on two variables, n and r. The Stirling number S(n, r)is the number of ways of partitioning a set of n members into r blocks(with no block empty, and the order of the blocks and within the blocks, is immaterial).(Strictly these are called Stirling numbers of the second kind. Those of the first kind,which are related, count something quite different, namely the number of ways we can permute n objects into r cycles.)For instance, the set with members a, b, c can be partitioned into three blocks injust one way:{a},{b},{c}, into two blocks in three ways{a, b},{c};{a},{b, c}, and{a, c},{b}, and into a single block in one way only:{a, b, c};it follows that S(3,1)=1, S(3,2)=3 and S(3,3)=1. Since a set of n members can be partitioned in only one way into either 1 block or into nblocks, we always have S(n,1)=1=S(n, n). Ifwe draw up the triangle of Stirling numbers after the fashion of Pascal’s Triangle, we arrive at the array of Figure 5, and we now explain how the triangle is generated.

5. Stirling's Triangle

Once again, the numbers satisfy a recurrence relation, meaning that each can be related to earlier ones in the array. Indeed, as with the binomial coefficients, each Stirling number can be obtained from the two above it, but it is not simply the sum. What is more, the row symmetrywe saw in the Arithmetic Triangle that generates the binomial coefficients is not present in Stirling’s Triangle. For example, S(5,2)=15 but S(5,4)=10. The rule of recurrence is simple enough, however. The entry 90, for example,is equal to 15+3×25. This is indicative of the general situation:to find a number in the body of the triangle, take the two immediately above it, and add the first to the second multiplied by the number of theposition in the row you are at.(This time, unlike the Arithmetic Triangle, start your row count at 1.)In a similar way, the entry S(5,4)=10=6+4×1. It is only the part of the rule in italics that differs from that of the Arithmetic Triangle. That is enough, however, to make the study of Stirling numbers considerably more difficult to that of the binomial coefficients. For instance, we derived a simple explicit formula for each binomial coefficient in terms of the factorials. Similarly, there is a formula for the nth Fibonacci number in terms of powers of the Golden Ratio, but nothing of the kind exists for Stirling numbers.

The recurrence rule is not hard to explain. We argue similarly to that for the recursion for the binomial coefficients, and by doing so recover the recurrence outlined above that is identical in form except for a single multiplier. In order to form a partition of a set of size n into r non-empty blocks, we may proceed in two distinct ways. We may take the first n-1 elements of the set and partition it into r-1 non-emptyblocks in S(n-1, r-1)ways, and the final member of the set will then form the rth block. Alternatively, we may partition the first n-1 elements of the set into r non-empty blocks, which can be done in S(n-1, r)ways, and then decide in which of the r blocks to place the final member of the set, giving a multiplier of r to that number. Hence we infer that

S(n, r)=S(n-1, r-1)+rS(n-1, r)forn=2,3,…

Using this recursion formula, we may calculate each line of the Stirling Triangle from the one above it. For example, putting n=7and r=5 we obtain:

S(7,5)=S(6,4)+5S(6,5)=65+5×15=65+75=140.

We can compute S(n,2)and S(n, n-1)directly from the definition as follows. An arbitrary partition of the n-set into a first set and a second set is described by a binary string of length n,where the presence of a 1 indicates presence in the first set and a 0in the second(in a similar wayto howwe showed that the number of subsets of an n-set is 2n). There are therefore 2n such ordered pairs of sets. Since, however, there is no ordering of the blocks within a partition, we divide this number by 2 to find the number of partitions of the n-set into 2 sets, giving the number 2n-1.Finally, we need to subtract 1 from this in order to exclude the case where one of the sets is empty;hence S(n,2)=2n-1-1. You can check that this represents the second diagonal line of numbers1,3,7,15,31,63,…running from the top right to the bottom left in Figure 5.

The sum of any row of the Arithmetic Triangle gives the corresponding power of 2–the number of subsets of a set of a given size. Similarly, summing the nth row of Stirling’s Triangle gives the number of ways of breaking a set of n objects into blocks,and this is called the nth Bell number.

Partition numbers

Ifon the other hand, the n objects of the set to be partitioned are identical, and so cannot be distinguished from one another, the number of ways of splitting the whole collection up into blocks is a much smaller integer, known as the nthpartition number. A particular partition corresponds to writing n as a sum of positive integers, without regard to order:for example,1+1+1+1+1 is one partition of 5 and there are six others, for we can also represent5 as 1+1+1+2,1+2+2,1+1+3,2+3,1+4, orsimply as 5. Therefore the 5th partition number is 7(that compares to the5th Bell number, which from the Stirling Triangle is seen to be1+15+25+10+1=52). There is no simple exact formula for the nth partition number–there is a complex one, which is itself based on a beautiful approximation due to the Indian genius Srinivasa Ramanujan(1887–1920).One simple symmetry regarding partitions is that the number of partitions of n into mparts is equal to the number of partitions of n in which the largest part is m. One way of seeing that this is true is through the Ferrar’sgraph(or Young diagram)of the partition,which is no more than the representation of the partition as a corresponding array of dots in which the rows are listed by decreasing size.

In the example shown in Figure 6 we have represented 17partitioned as 5+4+4+2+1+1. Note how the columns are also listed in decreasing order from left to right. If we reflect the array along the diagonal running from top left to bottom right, we recover a second Ferrar’s graph as shown, which can be interpreted as the partition 17=6+4+3+3+1. A similar reflection of the second graph returns you to the first and we say that the two corresponding partitions are dualto one another.This symmetry allows us to see that the numbers of partitions of two corresponding types are equal:the dual of a partition in which m, say, is the largest number(so the top row has mdots)is a partition with mrows, which corresponds to a partition into m numbers. For example, the number of partitions of 17 into 6numbers therefore equals the number of partitions of 17 in which6 is the largest number that occurs.

6. Dualpartitions of 17=5+4+4+2+1+1=6+4+3+3+1

Hailstone numbers

Although not a counting tool, the hailstone numbers are intriguing as they are also dened recursively but have more of a avour of the aliquot sequences that we met in Chapter 3. The following question goes by several names, the Collatz Algorithm,the Syracuse Problem, or sometimes just the 3n+1-problem, and it is simply the observation that, beginning with any number n, the following process always seems to end with the number 1. If n is even, divide it by 2, while if n is odd, replace it by 3n+1. For example, beginning with n=7 we are led by the rules through the following sequence:

7→22→11→34→17→52→26→13→40

→20→10→5→16→8→4→2→1

And so the conjecture is true for n=7, and indeed it has been veried for all n up beyond a million million. Things are different if youddle with the rules:for instance, replacing 3n+1 by 3n-1results in a cycle:

7→20→10→5→14→7→….

The sequences of numbers that arise from these calculations behave like hailstones in that they rise and fall erratically over a long period but eventually, it seems, always hit the ground. Of the first 1000 integers, more than 350 have a hailstone maximum height of 9232 before collapsing to 1. This will happen once you run into a power of 2, for they are exactly the numbers that cause you to fall straight down to ground level without encountering any more updrafts.

All sorts ofintriguing features can be discerned in graphs and plots based on the hailstone sequences reminiscent ofother chaotic patterns that arise in maths and physics. Typing‘hailstone numbers'into your favourite search engine will provide you with a wealth ofinformation, often intriguing, sometimes speculative,but generally inconclusive.