Jump to ContentJump to Main Navigation
Combinatorics: Ancient and Modern$

Robin Wilson and John J. Watkins

Print publication date: 2013

Print ISBN-13: 9780199656592

Published to Oxford Scholarship Online: September 2013

DOI: 10.1093/acprof:oso/9780199656592.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use.  Subscriber: null; date: 04 April 2020

The arithmetical triangle

The arithmetical triangle

Chapter:
(p.167) Chapter 7 The arithmetical triangle
Source:
Combinatorics: Ancient and Modern
Author(s):

A. W. F. EDWARDS

Publisher:
Oxford University Press
DOI:10.1093/acprof:oso/9780199656592.003.0008

Abstract and Keywords

The arithmetical triangle is the most famous of all number patterns. Apparently a simple listing of the binomial coefficients, it contains the triangular and pyramidal numbers of ancient Greece, the combinatorial numbers that arose in the Hindu studies of arrangements and selections, and (barely concealed) the Fibonacci numbers from medieval Italy. It reveals patterns that delight the eye, raises questions that tax the number-theorists, and amongst the ‘… coefficients, there are so many relations present that when someone finds a new identity, there aren’t many people who get excited about it any more, except the discoverer!’

Keywords:   arithmetical triangle, binomial, triangular numbers, pyramidal numbers, Fibonacci numbers

The arithmetical triangle is the most famous of all number patterns. Apparently a simple listing of the binomial coefficients, it contains the triangular and pyramidal numbers of ancient Greece, the combinatorial numbers that arose in the Hindu studies of arrangements and selections, and (barely concealed) the Fibonacci numbers from medieval Italy. It reveals patterns that delight the eye, raises questions that tax the number-theorists, and amongst the coefficients ‘There are so many relations present that when someone finds a new identity, there aren’t many people who get excited about it anymore, except the discoverer!’ [ 1 ].

Permutations and combinations

As we have seen in earlier chapters, many combinatorial enumeration problems involve the combinatorial numbers C(n, r), for n = 1,2,… and r = 0, 1,…, n, because these enumerate both the combinations of r things selected from n different things, and the arrangements or permutations of r things of one kind and nr of another kind. The notation indicates that these numbers are both combinatorial numbers and binomial coefficients, and a moment’s reflection shows the connection between them, for when we expand the binomial expression (a + b)n the coefficient of arbn−r enumerates the number of arrangements of r as and nr bs.

(p.168) When the coefficients are arranged in successive rows for each n, the arrangement is known as the arithmetical triangle, after the title of Pascal’s book Traité du Triangle Arithmétique (Treatise on the Arithmetical Triangle). The common arrangement shown below is not the one that Pascal used as the frontispiece to his book, where the coefficients for each n are displayed as diagonals, but it has nevertheless become customary to refer to it as Pascal’s triangle. As we have seen, there is no implication in this usage that Pascal was the earliest to record it; the eponym arises rather because Pascal was the first author to explore its properties in a systematic manner, identifying the binomial and combinatorial numbers with the figurate numbers (natural numbers, triangular numbers, tetrahedral numbers,…) of antiquity. For more information about the arithmetical triangle, see [2].

The arithmetical triangle

The usual form of Pascal’s triangle.

The combinatorial numbers in India

The connection between the arithmetical triangle and combinatorial problems was first made in India. As we saw in the Introduction and Chapter 1, Piñgala, a writer on prosody who flourished around 200 Bc, gave a rule, by all accounts very cryptically, for finding the number of combinations of n syllables, each of which could be either short or long, when these are taken one at a time, two at a time, three at a time, …, all at a time. It seems to have amounted to the observation that the natural numbers give the answers to the first question for successive values of n, the triangular numbers give the answers to the second question, the tetrahedral numbers give the answers to the third question, and (p.169) so on, through the ascending orders of the figurate numbers. The successive orders of the figurate numbers are given by the rows of Pascal’s format for the arithmetical triangle, each row being formed from its predecessor by summation, implying the well-known addition rule for binomial coefficients,

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

Piṅgala’s rule, known as the meru prastāra (the holy mountain), was most succinctly given by his commentator Varāhamihira, who in AD 505 wrote:

It is said that the numbers are obtained by adding each with the one which is past the one in front of it, except the one in the last place.

In the 10th century, Halayudha explained the rule in a way that corresponds to the usual modern form of the arithmetical triangle:

Draw a square. Beginning at half the square, draw two other similar squares below it; below these two, three other squares, and so on. The marking should be started by putting 1 in the first square. Put 1 in each of the two squares of the second line. In the third line put 1 in the two squares at the ends and, in the middle square, the sum of the digits in the two squares lying above it. In the fourth line put 1 in the two squares at the ends. In the middle ones put the sum of the digits in the two squares above each.Proceed in this way. Of these lines, the second gives the combinations with one syllable, the third the combinations with two syllables, etc.

This rule therefore develops the arithmetical triangle, using the addition formula to give the number of permutations of r things of one kind and nr of another.

The rule for the number of combinations of r things taken from n different things,

C ( n , r ) = n 1 × n 1 2 × n 2 3 × × n r + 1 r ,

was given algorithmically by the Jain mathematician Mahāvīra in Gaṇitasārasaṅgraha (Epitome of the Essence of Calculation), written in 850. This rule was repeated in the famous Līlāvatī of the Hindu mathematician Bhāskara II in 1150, who took n = 6 as an example: six tastes that are to be combined in all possible ways (sweet, pungent, astringent, sour, salty, and bitter). To apply the rule he set down the numbers 1, 2, 3, 4, 5, 6, forwards and backwards in the pattern

6 5 4 3 2 1 1 2 3 4 5 6 ,

(p.170) and by successive application of the rule found the numbers of preparations that combine these six tastes to be 6, 15, 20,15, 6, and 1, respectively. In so doing he listed the row of the arithmetical triangle for n = 6, lacking only the initial 1 corresponding to tastelessness. In another example he generated the row for n = 8.

Bhāskara also knew that C(n, r) gives the number of permutations of r things of one kind and nr of another, using as an example the enumeration of the arrangements of six syllables of which a given number are short and the remainder long, and in this case he noted that we must not forget the arrangement ‘all short’, making 64 arrangements in all. But he did not give the additive rule of the meru prastāra, and thus did not reveal how to generate a row of the arithmetical triangle from its predecessor.

However, another commentator, Bhat.t.otpala (1068), gave an example involving the combination of sixteen things, explicitly generating the arithmetical triangle, and added that the number of combinations could be found by either rule – that is, by successive additions, or by the above ‘multiplicative formula’ for C(n, r). Not until 1570 was this connection to be noted in the West. Here is Bhaṭṭotpala’s example illustrating the meru prastāra rule (this table also appears in Chapter 1 as given by Varāhamihira):

Taken twoat a time

Taken threeat a time

Taken fourat a time

16

15

120

14

105

560

13

91

455

1820

12

78

364

1365

11

66

286

1001

10

55

220

715

9

45

165

495

8

36

120

330

7

28

84

210

6

21

56

126

5

15

35

70

4

10

20

35

3

6

10

15

2

3

4

5

1

1

1

1

(p.171) By the start of the second millennium, therefore, we find in India the combinatorial numbers derived for the two simplest problems of permutations and combinations by the two algorithmic routes of multiplication and addition, the latter method generating the arithmetical triangle. In Līlāvatī Bhāskara went further, giving the multinomial coefficient for the number of arrangements when there are more than two kinds of things to choose from.

Combinatorial numbers in the West before Pascal

As we saw in Chapter 4, Levi ben Gerson, who lived in France, wrote on permutations and combinations in 1321, and gave in words the multiplicative formula for C(n, r) for the number of combinations of n things taken r at a time, deriving the result directly from the number of arrangements of n things taken r at a time, divided by the number of arrangements of r things. Before then, there had been several examples of Islamic arithmetical triangles (see Chapter 3). But it was not until the 16th century that the arithmetical triangle made its combinatorial debut in the West, in the General Trattato di Numeri et Misure (General Treatise on Numbers and Measures) of Niccolò Tartaglia.

Tartaglia sought the number of possible combinations when a number of six-sided dice are thrown. Occasional earlier enumerations had not revealed the essential structure of the solution, but Tartaglia found the connection with the figurate numbers ‘on the first day of Lent, 1523, in Verona’, as he proudly tells us, ‘having thought about the problem all night’. His General Trattato was published in 1556, and gives the solution as the first six columns of an arithmetical triangle in Pascal form. Tartaglia probably obtained his result by a clever ordering of the possibilities which facilitated a systematic enumeration, leading to the figurate numbers. He clearly knew the addition rule and the identity between the figurate numbers and the binomial coefficients. He gave the more usual form of the arithmetical triangle for them later in his book; in Italy, ‘Pascal’s triangle’ is sometimes known as ‘Tartaglia’s triangle’.

(p.172)

The arithmetical triangle

Tartaglia’s arithmetical triangle.

Meanwhile, in Germany, in 1544, Michael Stifel had presented a form of the arithmetical triangle based on the figurate numbers in connection with the extraction of roots, for which he needed to find the binomial numbers. His method was to write the natural numbers 1, 2, 3, 4, in the first column. Then, in the second column, beginning next to the 3, he wrote the triangular numbers 3, 6, 10, 15, (and he explicitly named them as such). For the third column, next to the 10, he then wrote the tetrahedral numbers 10, 20, 35, 56, – and so on, using the additive procedure for the triangle.
The arithmetical triangle

Stifel’s triangle of figurate numbers.

(p.173) From 1570, when Cardano’s Opus Novum de Proportionibus Numerorum (New Work on the Proportions of Numbers) appeared, the combinatorial application of the arithmetical triangle entered the mainstream of mathematics. Cardano gave the rule for getting from C(n, r — 1) to C(n, r), known to the Hindus, thus generating the multiplicative formula as well as the identification with the figurate numbers and their additive property.

The arithmetical triangle

Cardano’s arithmetical triangle.

The arithmetical triangle

Mersenne’s arithmetical table.

(p.174) By 1636 Father Marin Mersenne had learnt everything that Cardano had written on combinations, and in his Harmonicorum Libri XII (Twelve Books of Harmonic Principles) published the largest arithmetical triangle extant: twenty-five rows and twelve columns. Mersenne was familiar with the multiplicative formula and with its combinatorial derivation given by ben Gerson and, as we saw in Chapter 5, applied his combinatorial knowledge to the permutations and combinations of musical notes. The Pascals, father and son, visited him, and it is not surprising that Blaise Pascal’s format for the arithmetical triangle is the same as Mersenne’s, as Cardano’s, and ultimately as Tartaglia’s. To Pascal’s use of the arithmetical triangle we now turn.

Pascal’s Traité du Triangle Arithmétique

Pascal’s treatise on the arithmetical triangle is recognizably modern. He first established the properties of the binomial coefficients (as the entries of the arithmetical triangle are now universally called) and then, in several appendices, he showed how they could be used to solve a number of mathematical problems. The Traité was written in 1654, but was not distributed until 1665, after Pascal’s death, when the printed sheets were found amongst his papers; a complete description of Pascal’s book is given in [2, Ch. 6 and 7]. The appendix that concerns us is ‘Usage du triangle arithmétique pour les combinaisons’ (Use of the arithmetical triangle for combinations). It is preceded by an account of the figurate numbers, and is followed by Pascal’s famous solution to the problem ofpoints – a gambling problem concerning the division of stakes between two players when a game is left unfinished (see Chapter 6), thus introducing the notion of expectation.

The arithmetical triangle

Blaise Pascal(1623–1662)

(p.175)

The arithmetical triangle

Title page of Pascal’s Traité du Triangle Arithmétique.

Pascal starts:

The word Combination has been used in many different senses, so that to avoid ambiguity I am obliged to say what I mean by it

– and he gives its modern meaning. After some further preliminary remarks he presented his important Lemma 4:

the number of combinations of n + 1 things taken r + 1 at a time is equal to the sum of the number of combinations of n things taken r at a time and the number of combinations of n things taken r + 1 at a time

–that is,

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

For, said Pascal, using an example,

consider any particular one of the n + 1 things: C(n, r) gives the number of combinations that include it whilst C(n, r + 1) gives the number that exclude it, the two numbers together giving the total.

(p.176) Pascal may well have seen the first part of this reasoning in Pierre Hérigone’s Cours Mathématique (Course in Mathematics) of 1634.

Having thus established the addition formula by a direct combinatorial argument, Pascal pointed out that the same formula generates the arithmetical triangle, since the initial conditions correspond as well, and therefore that the triangle can be used to solve combinatorial problems.

Conclusion: By the rapport [Pascal’s word] which exists between the elements of the arithmetical Triangle and combinations, it is easy to see that everything which has been proved for the one applies to the other in like manner, as I shall show in a little treatise I have done on Combinations.

This is presumably his associated Latin treatise Combinationes, the first part of which is a Latin version of the above, whilst the remainder interprets some of the ‘consequences’ of the arithmetical triangle given in the first part of the Traité du Triangle Arithmétique in the language of combinations. Although it contains no surprises, it stands as the first systematic application of the arithmetical triangle to combinatorial problems.

Pascal’s solution to the problem of points follows as the next section of his Traité. Although it involves the arithmetical triangle, its great importance in the history of probability is not due to the solution of any further combinatorial problems (see [2, Appendix 1]).

It is interesting to note that Pascal seemed averse to using any argument involving n! as the number of permutations of n different things; it is almost as though he felt that he had a mission to develop the theory of combinations without using it, and he certainly never gave it. When his friend M. de Gaignières challenged him to find an explanation of the multiplicative formula, he said that because of the difficulty he thought it proper to leave the demonstration to him; ‘however, thanks to the Arithmetical Triangle, an easy way was opened up’, and he pointed out the identity in one of the ‘consequences’ of his book.

De Montmort and Jacob Bernoulli

It is from Pierre de Montmort that Pascal probably acquired the credit for thearithmetical triangle, for de Montmort’s book Essay d’Analyse sur les Jeux deHazard (Essay on the Analysis of Games of Chance), whose principal edition is (p.177) dated 1713, starts with a seventy-two page Traité des Combinaisons (Treatise on Combinations) which relies on Pascal’s Traité. In his introduction, de Montmort wrote that

Pascal has proceeded furthest, as is clear from his treatise The Arithmetical Triangle, which is full of observations and discoveries on the figurate numbers of which I believe him to be the originator, since he does not cite any other person.

Already in its first edition in 1708, de Montmort had given the combinatorial explanation for C(n, r), which we earlier attributed to ben Gerson. Unlike Pascal, de Montmort proceeded by revealing patterns of enumeration that enabled him to identify numbers of combinations with the figurate numbers (and hence the arithmetical triangle), but much of his Traité was devoted to combinatorial problems that cannot easily be solved in terms of the numbers in the triangle. One problem that did lead to the triangle was Tartaglia’s dice problem, which de Montmort solved by enumeration, describing it as ‘curious enough, it seems to me’, and which is the same problem as finding the number of terms in the power of a multinomial.

The arithmetical triangle

Title page of Jacob Bernoulli’s Ars Conjectandi.

(p.178) Part Two of Jacob Bernoulli’s Ars Conjectandi (Art of Conjecturing) of 1713 is Doctrina de Permutationibus & Combinationibus (A Treatise on Permutations and Combinations), which was written in apparent ignorance of Pascal’s Traité. The arithmetical triangle makes its appearance in Chapter III as the solution to the number of combinations, enumeration being along the same lines as de Montmort’s. Bernoulli waxed lyrical about it:

This Table has truly exceptional and admirable properties; for besides concealing within itself the mysteries of combinations, as we have seen, it is known by those expert in the higher parts of mathematics also to hold the foremost secrets of the whole of the rest of the subject.

He then listed twelve ‘wonderful properties’ of the triangle, rather as Pascal had done, concluding with a proof of the multiplicative formula which is longer and less elegant than Pascal’s. Like Pascal, he failed to provide a direct combinatorial proof.

The outstanding contribution of Part Two is the derivation of the coefficients of the polynomials for the sums of the powers of the integers, with which Bernoulli ended Chapter III (see Chapter 6). Although this relies on the figurate numbers, the argument is not combinatorial; further information can be found in [2, Ch. 10 and Appendix 3].

In the remaining chapters of Part Two of his Ars Conjectandi, Bernoulli dealt with a number of combinatorial problems in ways by now familiar, but mention may be made of the arithmetical triangle that appears in Chapter IV in connection with the problem of points. Bernoulli here added nothing to Pascal’s solution. In Chapter V there is another arithmetical triangle, this time presenting the number of combinations of r things from n different kinds of things, repeats being allowed. The result was obtained by a clever systematic enumeration that demonstrates the applicability of the addition rule for figurate numbers, and Bernoulli then gave a combinatorial explanation for this rule. The problem is identical to that solved by Tartaglia, which we discussed earlier. In Chapter VIII Bernoulli remarked, like de Montmort, that it is also the solution to the problem of finding the number of terms in the power of a multinomial:

It is proper here to note the peculiar sympathy between combinations and powers of multinomials.

In the introduction to Part Two, Bernoulli mentioned the names of van Schooten, Leibniz, Wallis, and Prestet as having preceded him. Amongst these (p.179) authors we remark only that Leibniz, in his youthful Dissertatio de Arte Combinatoria of 1666, repeated the combinatorial argument that (unknown to him) Pascal had already used in his Traité to obtain the addition relation in the arithmetical triangle. Leibniz presented a table of the triangle up to n = 12; the many further contributions he made to combinatorial theory were discussed in Chapter 6.

From binomials to multinomials

The arithmetical triangle naturally generalizes to more dimensions, corresponding to the generalization of binomial coefficients to multinomial coefficients. The rule is that the number of permutations of a things of one kind, b of a second kind, c of a third kind, and so on, n things all told, is equal to

n ! a ! b ! c ! .

This rule first appeared in the West in the work of Mersenne in 1636, and was later explained by Wallis in 1685. As we mentioned earlier, Bhāskara had already given it in the East in his Līlāvatī. On 16 May 1695 Leibniz wrote to Johann Bernoulli announcing a ‘wonderful rule’ for the coefficients of the powers of a multinomial, to which Bernoulli replied on 8 June giving the above formula and adding

It would be a pleasure to see your rule and it would be well to test whether they agree; yours is possibly simpler.

(In fact it was slightly more complicated.) De Moivre published this multinomial coefficient in 1698, observing simply that it gives the number of permutations of the elements making up a given term.

Notes:

(1.) D. E. Knuth, The Art of Computer Programming, Vol. I, Fundamental Algorithms (2nd edn.), Addison-Wesley (1973), 53.

(2.) For a full history of the arithmetical triangle and its influence in the development of mathematics in general, and for references to all the writers mentioned in this chapter, see A. W. F. Edwards, Pascal’s Arithmetical Triangle, Johns Hopkins University Press (2002). This second edition contains an epilogue and a third appendix not present in the first edition (Charles Griffin & Co., Ltd, and Oxford University Press (1987)).

(p.180) The epilogue lists a number of books and articles that had appeared since 1987, or which were earlier than 1987 but originally overlooked. The most significant oversight was the excellent translation of Pascal’s Traité and his correspondence with Fermat in Great Books of the Western World 33: The Provincial Letters, Pensées, Scientific Treatises by Blaise Pascal (Encyclopaedia Britannica, 1955, 1963). Cambridge University Library has digitized one of its copies of the Traité at www.lib.cam.ac.uk/RareBooks/PascalTraite/.

Appendix 3 is a commentary on the Introduction and Chapters I–III of Bernoulli’s Ars Conjectandi, Part Two: The theory of permutations and combinations, and in particular contains descriptions of some of the proofs in Bernoulli’s Chapter III. In 2006 the first complete translation into English of Ars Conjectandi was published: J. Bernoulli, The Art of Conjecturing, together with Letter to a Friend on Sets in Court Tennis, translated with an introduction and notes by Edith Dudley Sylla (Johns Hopkins University Press). Some remarks relevant to combinatorics are in A. W. F. Edwards’s review of this translation in The Mathematical Intelligencer 29 (2007), 70–2.