The beginnings of combinatorics in India date back to Bharata's Natyasastra and the last chapter of the work Chandahsastra (Sanskrit Prosody) by Pingala (c. 300 BCE). Pingala deals in a few cryptic sutras with the combinatorics underlying the metres of Vedic Hymns and classical Sanskrit poetry. Metre is the basic rhythmic structure of a verse, here characterised by a finite sequence of syllables, some short and some long. We recall that syllables are irreducible units of speech, some being short like ka and some being long like kaa. We define the length of a metre as the number of its constituent syllables. We shall abbreviate a short syllable by l and a long syllable by g. For example, the length of a metre gll is 3.
Pingala gives a method of enumeration, which is called prastara, of metres of a given length n (which indeed are 2n in number), using a recursive procedure.
For example, the prastara of metres of length 1 is g, l (which are displayed as an array with two rows). According to Pingala, the prastara of metres of length 2 is obtained from the above by adding a g to the right of the prastara above, and then an l to this prastara, so that we get gg; lg; gl; ll (which are displayed as an array with four rows). The prastara of metres of length 3 is the array comprising the eight rows ggg; lgg; glg; llg; ggl; lgl; gll; lll which is obtained from the prastara of metres of length 2 above by adding first a g and then an l to the right. The above recursive procedure is then continued.
In this remarkable manner, Pingala's method leads one to a construction of the binary expansion of integers, by setting g = 0 and l = 1 in the successive rows of the prastara, the fifth row of the prastara of length n being a mnemonic for the binary expansion of i — 1.
For example, the 5th row ggl in the prastara of the metres of length 3 stands for the binary expansion 0:1 + 0:2 + 1:22 of 4. The last row, that is, the (2n — 1)-th row, of the prastara of metres of length n is ll; … l which yields the formula 1 + 2 + + 2n - 1 = 2n — 1:
With the advent of Prakrit and Apabhramsa poetry, came the idea of extending the above theory to matra metres where the value of a long syllable g is assumed to be 2 and that of a short syllable l is assumed to be 1, the value of the metre being defined to be the sum of the values of its constituent syllables. The construction of the prastara of metres of value n is achieved as above by a recursive procedure which is more subtle. The prastara of metres of value 1 is l; that with value 2 is g; ll; the prastara of metres of value 3 is obtained from these two by adding a g to the right of the prastara of metres of value 1 to get lg, and an l to the right of the prastara of metres of value 2 to get gl; lll; thus the prastara of metres of value 3 is lg; gl; lll. Similarly, we can write down the prastaras of metres of value n, using the prastaras of metres of value n _ 1 and n _ 2. If sn is the number of elements of in the prastara of metres of length n, we have s1 = 1; s2 = 2, and for n _ 3, sn = sn_1 +sn_2. This relation was noticed by Virahanka (c.600 CE).
The study of matra metres thus led the ancient Indian mathematicians to the sequence sn = 1, 2, 3, 5, 8, …, (what is generally known as the Fibonacci sequence, though discovered centuries before Fibonacci). As in the case of binary expansions, we obtain now unique expansions for natural numbers in terms of the Fibonacci numbers.
Combinatorics evolved in time not merely to apply to Sanskrit prosody but to many other problems of enumeration: in medicine by Sushruta, perfumery by Varahamihira, music by Sarngadeva (which shall be briefly discussed below), and so on.
Sarngadeva (c.1225 CE), who lived in Devagiri in Maharashtra, under the patronage of King Singhana, wrote his magnum opus Sangitaratnakara, a comprehensive treatise on music which gives in its first chapter a prastara enumerating all the 7! = 7_6_5_4_3_2_1 = 5040 permutations of the swaras S;R; G;M; P;D;N. The prastara of a single swara is S, that of two swaras S;R, is SR;RS; the prastara of three swaras, S;R;G is SRG;RSG; SGR;GSR;RGS;GRS:
More generally, the prastara of all the seven swaras, starts with the swaras in the natural order SRGMPDN and ends in the last or the 5040th row with the swaras in the reverse order, NDPMGRS, and the intermediate rows are constructed by a rule formulated by Sarngadeva.
It is indeed a remarkable fact that if we start more generally with n elements a1; a2; _ _ _ an and arrange their permutations in a prastara following Sarangadeva's rule, the ith row of the prastara is a mnemonic for a unique expansion of i; 1 _ i _ n!, as a sum of factorials, i = 1 _ 0! + c1 _ 1! + c2 _ 2! + _ _ _ + cn_1 _ (n _ 1)!; (with the convention 0! = 1), where the coefficient cj of j! lies between 0 and j _ 1. In particular, we have the beautiful formula n! = 1 _ 0! + 1 _ 1! + 2 _ 2! + _ _ _ + (n _ 1) _ (n _ 1)!; implicit in the work of Sarngadeva.
Indian combinatorics continued to flourish till the 14th century, when the celebrated mathematician Narayana Pandita wrote his comprehensive Ganitakaumudi (“Moonlight of Mathematics") in 1356 CE, placing the earlier work on combinatorics in a general mathematical context. He has in this great work a chapter on magic squares entitled Bhadraganita, where among other things, he constructs a class of 384 pan-diagonal 4 _ 4 magic squares with entries 1; 2; 3; _ _ _ ; 16.
We recall that in a magic square, the numbers in the rows, columns and diagonals sum to the same magic total. In a pan-diagonal magic square, the broken diagonals also yield the same magic total.
Succinctly put, pan-diagonal magic squares have the remarkable property that they can be considered as a magic squares “on the torus". It is of interest to note that Rosser and Walker proved in 1936 (the proof was simplified by Vijayaraghavan in 1941) that there are only 384 pan-diagonal 4 _ 4 magic squares with entries 1; 2; _ _ _ ; 16.
Curiously enough, Ramanujan, in his Notebooks of probably his earliest school days, has the magic square
1 14 11 8
12 7 2 13
6 9 16 3
15 4 5 10
This turns out to be one of the 384 magic squares considered by Narayana Pandita. (Notice that rows, columns, diagonals and broken diagonals add to 34. For example, 5+3+12+14 = 12 + 9 + 5 + 8 = 34).
Xenophanes, the founder of the Eleatic School of Philosophy, had the well known dictum - Ex nihilo nihil fit, “Out of nothing, nothing comes." One wonders whether after all Ramanujan was indeed influenced somewhat by the mathematical tradition of his ancestors.
(The author is an Adjunct Professor with the Chennai Mathematical Institute)