A modern glance at Nārāyaṇa-paṇḍita’s combinatorics-1

For improved reading experience one may use the PDF version.

Students of the history of Hindu mathematics are well-acquainted with Nārāyaṇa-paṇḍita’s sophisticated treatment of various aspects of combinatorics and integer sequences in his Gaṇita-kaumudī composed in 1356 CE. In that work he gives about 43 problems relating to combinatorics. Continuing with our study of various aspects of Nārāyaṇa’s work using a modern lens, in this note we shall look at some of his problems in combinatorics and what a modern (low level) student can learn from them.

The first problem we shall look at introduces a student to the discrete factorial function n! using a verse in the Vasantatilakā meter;
cāpeṣu khaḍga-ḍamarūka-kapāla-pāśaiḥ khaṭvāṅga-śūla-phaṇi-śakti-yutair bhavanti ।
anyonya-hasta-kalitaiḥ kati mūrtibhedāḥ śambho harer iva gadā’ri-saroja-śaṅkhaiḥ ॥
With a bow (1), an arrow (2), a sword (3), a double-drum (4), a skull (5), a lasso (6), a skull-topped rod (7), a trident (8), a snake (9) and a spear (10) — by changing them from one hand to another how many different images of Rudra come to be? Likewise, of Viṣṇu with a mace (1), a wheel (2), a lotus (3) and a conch (4).

For Rudra with 10 arms the answer is 10!=3628800, whereas for Viṣṇu it is 4!=24. This problem was well-known among earlier Hindu scientists and is not original to Nārāyaṇa. Here, he is merely reusing this verse without any change from Bhāskara-II’s Līlāvatī. In the case of Viṣṇu, each of these 24 permutations have a specific name starting from Keśava. There are correspondingly 24 forms of Lakṣmī. These forms are an important aspect of the Pañcarātra system where they are counted along with the 4 basic vyūha-s in the śuddha-mūrti-s (“Platonic” forms) in texts like the Nārada-pāñcarātra and are attested in iconography across the Indosphere. The general use of permutations in various endeavors is mentioned by Nārāyaṇa after he provides the procedure for writing out the permutations:
aṅka-prastāra-vidhiś caivaṃ mūrtiprabhedānām ।
sa-ri-ga-ma-pa-dha-nīty eṣāṃ vīṇāyā nikvaṇānāṃ ca ॥
This procedure generating the permutation of digits is also used in permutations of images [of deities], sa-ri-ga-ma-pa-dha-ni (the notes of Hindu music) and the notes produced by the vīṇā.

Problem-2 (A verse again in the Vasantatilakā meter):
dhātrī lavaṅga-dala-kesara nāga-railā vakraṃ kaṇāḥ samaricāḥ sasitā bhavanti ।
ekādibhiś ca militair gadināṃ katīha cūrṇāni bho vada gadāpanude gadajña ॥
O apothecary, how many different different disease-curing spice-powders come from mixing one etc (i.e. 1, 2, 3…) of gooseberry, clove, cinnamon, saffron, ginger, cardamom, Indian may apple (Sinopodophyllum hexandrum), cumin, pepper and sugar?

This type of problem is encountered widely in Hindu literature — we find a discussion of the combinations of tastes in the medical saṃhitā-s of Caraka and Suśruta. Subsequently, the great naturalist Varāhamihira in \sim 550 CE discussed the production of various perfumes by combinations of basic scents. Such combinations are also discussed by king Bhojadeva Paramāra in his chemical treatise in the 1000s of the CE. Related problems are also taken up in Bhāskara-II and by the polymath Śārṅgadeva in his musical treatise. This particular problem is rather typical of the combinations used in preparation of drugs in Āyurveda. As a pharmacological aside the Indian may apple if properly used can be quite effective treating tumors caused by certain papillomaviruses. Returning to the solution of the problem, we need to recall the formula for combinations:

{}^nC_k = \dfrac{n!}{k!(n-k)!}

Let N be the total number of powders that can be created via each set of combinations: by taking 1 at a time we get 10, by taking 2 at time we get {}^{10}C_2=45 and so on. Thus, we get:

N=\displaystyle \sum_{k=1}^{10} {}^{10}C_k=1023

nArAyaNa_combinations_Fig1Figure 1

In Hindu tradition, the study of combinations and their sum goes back to at least the Chandas-śāstra (the treatise on meters) of Piṅgala. This has been extensively discussed in the literature and we present it only briefly:

pare pūrṇam । pare pūrṇam iti । CS 8.34-35
Complete it by using the two distal ends. Repeat to complete using the distal flanking ends.

While these original sūtra-s of Piṅgala are difficult to directly understand, they have been explained in the glosses of several authors since (e.g. Kedāra-bhaṭṭa and Halāyudha). The two sūtra-s specify the construction of the Meru-prastāra or the combinatorial triangle. The first sūtra implies that you write out the flanking cells with 1 corresponding to row n:

1 \\ 1 \quad 1 \\ 1 \quad {. } \quad 1 \\ 1 \quad {. } \quad {. } \quad 1 \\ 1 \quad {. } \quad {. } \quad {. } \quad 1 \\ 1 \quad {. } \quad { .} \quad {. } \quad {. } \quad 1 \\

The second sūtra implies that you fill in the interior cell by repeating the procedure:

1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \\

While this is extensively discussed in the context of Chandas, one can also find a clear algorithm in Bhāskara-II’s Līlāvatī using the combination function to produce not just the combinatorial triangle (Meru) but also any row or cell of it. Thus, from the Meru we can write the formula for the expansion of a binomial as:

(x+y)^n=\displaystyle \sum_{k=0}^{n}{}^nC_k x^k y^{n-k}

This tells us that the null-product or 0!=1 (implicitly provided in Bhāskara-II’s algorithm: there only 1 way of not choosing anything). The magnitudes of the k^{th}-combination or the values assumed by the combination function for a given n as k changes determine the values of the individual terms of the above expansion. Hence, we use the problem-2 to introduce and illustrate to students the shape of the binomial distribution (Figure 1). Since the Meru itself can be seen as the triangle of (1+1)^n, we get the formula for the sum of combinations for a given n as,

N=\displaystyle \sum_{k=0}^{n} {}^{n}C_k=2^n

If we leave out the null combination k=0, we get N=2^n-1 as in the problem-2 where N=2^{10}-1.

As this note is part historical and part educational (for a low-level student), let us next consider another binomial expansion that played a cornerstone role in the origin of modern mathematics,

\displaystyle \lim_{n \to \infty} \left(1+\dfrac{1}{n}\right)^n

We can intuitively sense based on the easily-determined first 3 terms that it might converge to some number between 2 and 3 but what is that number? We can experimentally see that the above expression converges slowly: for n=10 we get 2.6; for n=100 we get 2.7; for n=200 we have 2.71. This is exactly where Jakob Bernoulli got to when he first encountered this problem and realized that it was converging to something around 2.71. However, we can do better by determining the limit:

\displaystyle \lim_{n \to \infty} \left(1+\dfrac{1}{n}\right)^n = \dfrac{1}{0! \cdot n^0}+ \dfrac{n}{1! \cdot n^1} + \dfrac{n\cdot (n-1)}{2! \cdot n^2}+ \dfrac{n\cdot (n-1) \cdot (n-2)}{3! \cdot n^3}...\\[10pt] = \dfrac{1}{n^0 \cdot0!}+ \dfrac{n}{n \cdot 1!} + \dfrac{n^2 \cdot (1-1/n)}{n^2 \cdot 2!}+ \dfrac{n^3\cdot (1-1/n) \cdot (1-2/n)}{n^3 \cdot 3! }...\\[10pt] = \dfrac{1}{0!}+ \dfrac{1}{1!} + \dfrac{(1-1/n)}{2!}+ \dfrac{(1-1/n) \cdot (1-2/n)}{3!}...

Taking the limit n \to \infty we get:

\displaystyle \lim n \to \infty \left(1+\dfrac{1}{n}\right)^n= \sum_{n=0}^{\infty} \dfrac{1}{n!}

Thus, our limit is the infinite sum of the reciprocal of the factorials. This is much faster-converging and with just 10 terms converges to 7 places after the decimal point to 2.7182818… The importance of this limit and the number it converges to comes to fore in another central result in the emergence of modern mathematics: What is the rate of change (derivative) of the logarithmic function? Let us start with a logarithm taken to some base b, i.e. y=\log_b(x). Hence,

\displaystyle \dfrac{dy}{dx}=\lim_{\delta x \to 0} \dfrac{\log_b(x+\delta x)-\log_b(x)}{\delta x} =\log_b\left( \dfrac{x+\delta x}{x}\right)^{1/\delta x} =\log_b\left( 1+\dfrac{\delta x}{x}\right)^{1/\delta x} \\[10pt] =\log_b\left( 1+\dfrac{\delta x}{x}\right)^{x/\delta x \times 1/x} =\dfrac{1}{x}\log_b\left( 1+\dfrac{\delta x}{x}\right)^{x/\delta x}

Now we can write \tfrac{\delta x}{x} as some \tfrac{1}{n}; \therefore \tfrac{x}{\delta x}=n. As \delta x \to 0, n \to \infty. Thus, we can rewrite our limit as:

\displaystyle \dfrac{d}{dx}y= \lim_{n \to \infty} \dfrac{1}{x}\log_b\left( 1+\dfrac{1}{n}\right)^{n}

We observe that this is the same limit we evaluated above. Now, if we define e as the sum of the reciprocal of the factorials, which is the limit, and set b=e then \tfrac{d}{dx}\log_e(x)=\tfrac{1}{x}. Thus, we get e to be the natural base of logarithmic function and the derivative of \log(x). Conversely, the area under a unit rectangular hyperbola, i.e y=\tfrac{1}{x} is the logarithmic function with base e.

Armed with e, we can next retrace certain developments in the history of early modern mathematics. What is the relationship of an arbitrary exponential curve y=a^x to e. For this we need to first determine the derivative of a^x. This is trivially done now that we have the derivative of \log(x):

y=a^x \; \therefore \log(y)=x \log(a)\\[10pt] \dfrac{d \log(y)}{dx}=\log(a)\\[10pt] \dfrac{d \log(y)}{dy}\cdot \dfrac{dy}{dx}=\log(a)\\[10pt] \dfrac{1}{y}\cdot \dfrac{dy}{dx}=\log(a)\\[10pt] \dfrac{dy}{dx}=y\log(x)=a^x \log(a)

exponentials_eFigure 2

With this in hand we can see the relationship of any exponential curve y=a^x to e (Figure 2):
\bullet Consider the family of exponential curves y=a^x (Figure 2; the red curve is y=e^x). From the above result we see that the tangent to a exponential curve will have the slope m=\log(a)a^x

\bullet Let x=\tfrac{1}{\log(a)}. Then: m=\log(a)a^{1/\log(a)}=\log(a)a^{\log(e)/\log(a)}=\log(a) a^{\log_a(e)}=e\log(a)

\bullet A line passing through origin has the equation y=mx. We set m=e\log(a); when x=\tfrac{1}{\log(a)} the equation of the line yields y=e. Similarly, the equation of the exponential curve yields y=a^{1/\log(a)}=e. Thus, the line y=e\log(a)x is the tangent to y=a^x from origin.

\bullet Thus, the tangent to an exponential curve from the origin will touch it at a height of e from the X-axis at x=\tfrac{1}{\log(e)}

Given the derivative of the exponential function, it is obvious that the derivative of e^x is e^x. This in turn allows one to establish the relationship of any power of e to the reciprocal of factorials. Consider the infinite series:

\displaystyle \textrm{f}(x)= \sum_{n=0}^{\infty} \dfrac{x^n}{n!}=1+x+\dfrac{x^2}{2}+\dfrac{x^3}{3!}+\dfrac{x^4}{4!}+...\\[10pt]\\ \dfrac{d \textrm{f}(x)}{dx} = 1+x+\dfrac{x^2}{2}+\dfrac{x^3}{3!}+...\\[10pt] \therefore \dfrac{d \textrm{f}(x)}{dx} = \textrm{f}(x)

Now the function whose derivative is the same as the function itself is e^x; hence,

\displaystyle e^x= \sum_{n=0}^{\infty} \dfrac{x^n}{n!}

Thus, this gives the relationship of a power of e to the reciprocal of factorials. If we put x=1 in the above we get the same infinite series for e as we obtained from the above limit. With this in hand, we can arrive at one of the most remarkable functions discovered in the history of early modern mathematics that is key to our understanding of the universe.

nArAyaNa_normal_Figure3Figure 3

In problem-2 we saw the magnitudes assumed by the combination function. We see that they appear to define a bell-shaped curve (Figure 2, 3). What is the curve that best approximates the binomial coefficients as n \to \infty (Figure 3; shown for n=50). For this we can begin by noting the following. It is a symmetric curve around the central or the highest value binomial coefficients. It falls sub-exponentially and is asymptotic to the x-axis. Given this we can try to construct this basic shape with its maximum centered on (0,1) using an infinite series approach (Figure 4). Given that it is symmetric, we only need to consider even powers of x in such a series.

bell_curve_expansionFigure 4

We start with y=\tfrac{x^0}{0!}. This in the least captures the maximum but little else. So the next term corrects this by a subtraction to get a curve around the maximum; thus y=\tfrac{x^0}{0!}-\tfrac{x^2}{1!}. However, this correct falls straight down and we have to add a term to get closer to the asymptotic behavior with respect to the X-axis. Thus we get: y=\tfrac{x^0}{0!}-\tfrac{x^2}{1!}+\tfrac{x^4}{2!}. We continue this process (first 8 steps are shown in Figure 4) and get the infinite series:

y=\displaystyle \sum_{0}^{\infty} \dfrac{\left(-x^2\right)^n}{n!}

From the above series for a power of e we can immediately see that:


This is the famous equation of the shape of the normal distribution, which is a limit of the binomial distribution as n \to \infty. With this we can now provide the continuous approximation for the combination function normalized by the maximal combination (Figure 3):


Thus for the actual combination function we get:


vadāśu rupādi navāvasānaiḥ ।
bhedām̐ś ca labdhy aṅka-mukhāntya-bhedān
ūrdhvāṅka-yogaṃ sakalāṅka-yogam ।
aṅka-prapātaṃ ca sakhe pṛthak te
vadā ‘ṅkapāśe ‘sti pariśramaś cet ॥
Snakes (8), fires (3), deficit (9): (9,3,8); two (2), guṇa-s (3), limbs [of Veda] (6), moon (1): (1, 6, 3, 2); starting from form (1) to nine (9): (1,2,3…9); Quickly state: (i) the number of permutations; (ii) the number of permutations either beginning or ending in one of those digits; (iii) sum of digits in a particular place; (iv) sum of all numbers [formed by permutation of the digits]; (v) the total number of digits; O friend state these for each set separately if you have labored on combinatorics.

Let n be the number of the objects participating in the permutations without replacement and s be those objects, in this case digits. Given this, the problem systematically takes you through several interesting questions:
(i) The bheda-s, i.e. permutations: n!. For s=1..9 it is 362880.

(ii) The aṅka-mukha-s or aṅkāntya-s, i.e. number of permutations that either begin or those that end in a particular digit: (n-1)!= \Gamma(n). This is so because we keep one position constant and allow the remaining to vary freely; thus, n-1 positions are available for permutation. For s= 1..9 it is 40320.

(iii) The ūrdhvāṅka-yoga, i.e. the sum of the numbers in a particular column. \Gamma(n) \cdot \sum s. From the above we saw that the number of permutations starting with a particular digit is \Gamma(n). Thus, for a given column, we will have that many permutations with each digit. Thus, \sum s multiplied with \Gamma(n) will give us the sum for a given column. For s= 1..9 it is 1814400

(iv) The sakalāṅka-yoga, i.e. the sum of all the numbers formed by the digit permutations. \Gamma(n) \cdot \sum s \cdot (\displaystyle \sum_{k=0}^{n-1} 10^k). We have the expression for the sum of a column from above. Now, consider a small example of the given problem with 3 digits. We can rewrite the numbers formed by the permutations to keep the same total thus:

\begin{matrix} 1 \quad 2 \quad 3\\ 1 \quad 3 \quad 2\\ 2 \quad 1 \quad 3\\ 2 \quad 3 \quad 1\\ 3 \quad 1 \quad 2\\ 3 \quad 2 \quad 1\\ \end{matrix} \; \to \; \begin{matrix} 1 \quad 1 \quad 1\\ 1 \quad 1 \quad 1\\ 2 \quad 2 \quad 2\\ 2 \quad 2 \quad 2\\ 3 \quad 3 \quad 3\\ 3 \quad 3 \quad 3\\ \end{matrix}

As a result we can express the sum of all numbers formed by the permutation of the digits to be the sum of a column multiplied by \sum_{k=0}^{n-1} 10^k; 111 for the above example. Thus, for s=1..9 we get 1814400 \times 111111111= 201599999798400.

(v) Finally, the aṅka-prapāta, i.e. the total number of digits in all the permutations. n^2\cdot \Gamma(n). Since there will be n! permutations and n starting digits it is easy to see that the total number of digits across all permutations will be the above expression. For s=1..9 it is 3265920.

One would have noticed that we have used \Gamma(n) for (n-1)!. When Gauss studied the continuous form of the factorial function he merely took it as x!; however, the French mathematician Legendre defined it using \Gamma(n)=(x-1)!. We take the Legendre definition of the famous Gamma function as it naturally emerges in solutions of problems such as that of Nārāyaṇa. Indeed, this definition also naturally emerges from the famous integral of Euler for \Gamma(x) that behaves just like the (n-1)! function. Being an integral this also gives the continuous form of the \Gamma(x) function specifying the value of the function for non-integer x. Euler’s integral:

\Gamma(x) = \displaystyle \int_0^\infty t^{x-1}e^{-t}dt

This integral can be handled using the rule for integration by parts:
\int f(x) \cdot g(x)dx = f(x) \int g(x) dx - \int f'(x) (\int g(x) dx) dx
Using f(x)=t^{x-1} and g(x)=e^{-t} we get:

\Gamma(x) = t^{x-1} \int e^{-t}dt - \int (x-1) t^{x-2} (\int e^{-t}dt) dt \\[7pt] = -t^{x-1} e^{-t} + (x-1)\int t^{x-2}e^{-t} dt

Taking the limits we get:

\Gamma(x) = \displaystyle \left. -t^{x-1} e^{-t} \right\rvert_{0}^{\infty} + (x-1) \int_{0}^{\infty} t^{x-2}e^{-t} dt\\[10pt] \therefore \Gamma(x) = (x-1)\Gamma(x-1)

By putting x=n and doing the above repeatedly we get \Gamma(n)=(n-1)(n-2)... until we reach 1 at which point the integral becomes:

\Gamma(n)=\displaystyle (n-1)(n-2)..2 \cdot 1 \int_{0}^{\infty} t^0 e^{-t} dt =(n-1)!

In the final part of this note we shall consider the integer sequence defined by the aṅka-prapāta: n^2\cdot \Gamma(n). Now let us do this for the sets of n=1, 2, 3, 4... permutable symbols. We get the integer sequence f[n]:
1, 4, 18, 96, 600, 4320, 35280, 322560, 3265920…

This sequence has a notable property. It defines the number of integers from 1..k! that are not divisible by k for k=2, 3, 4.... Why this is so is easy to apprehend: Since we start from 2, we have k=n+1. Now the numbers that will be divisible by k between 1..k! will amount to \tfrac{k!}{k}=(k-1)!=n!. Therefore, the numbers that will not be divisible by k will amount to (n+1)!-n!=n!(n+1)-n!=n (n-1)! (n+1-1)=n^2 \Gamma(n).

If we take the sum of the reciprocals of this sequence we see that it converges to a constant:

\displaystyle \sum_{n=1}^{\infty} \dfrac{1}{n^2 \Gamma(n)} = 1.3179021514544...

Now, what is this number? We discovered that this number emerges from the solution of an interesting definite integral:

\displaystyle \int_0^1 \dfrac{e^x-1}{x} dx= 1.3179021514544...

The integral can be split up as:

\displaystyle \int \dfrac{e^x}{x} dx - \int \dfrac{1}{x} dx= \int \dfrac{e^x}{x} dx -\log(x)+C

Eix_etcFigure 5

It is immediately apparent that the first integral \int \dfrac{e^x}{x} dx is a tricky one: the function y= \dfrac{e^x}{x} diverges to \infty as x^+ \to 0 (from positive side) and to -\infty as x^- \to 0 (from negative side). Remarkably, these opposite divergences cancel each other and the integral converges to a fixed value. Thus we can evaluate it to a given x as:

\textrm{Ei}(x) = \displaystyle \int_{-\infty}^x \dfrac{e^t}{t} dt

This function \textrm{Ei}(x) is the exponential integral with deep connections with permutations. The two divergences of y= \dfrac{e^x}{x} exactly cancel each other when x=\log(\mu)=0.37250741..., i.e. \textrm{Ei}(x)=0. This \mu=1.451369234 is the Soldner-Ramanujan constant that was first discovered by Johann von Soldner and independently by Ramanujan who arrived at it when he discovered multiple series for the logarithmic integral \textrm{Li}(x)=\int_0^x \tfrac{dx}{\log(x)} (Figure 5), which Gauss had shown to provide the asymptotic description of the distribution of prime numbers. The famed \textrm{Li}(x) = \textrm{Ei}(\log(x)). Returning, to our original integral we can thus write its indefinite solution as:

\displaystyle \int \dfrac{e^x-1}{x} dx= \textrm{Ei}(x) -\log(x) +C

Now we observe that as x^+ \to 0,\; \textrm{Ei}(x) \to \infty,\; \log(x) \to -\infty (we only consider the approach to 0 from positive side for only there the real \log(x) is defined). The two remarkably balance each other such that as x^+ \to 0 the above integral converges to \gamma=0.577215664..., which is the famous Euler-Mascheroni constant with a deep connection to the Gamma function (See below). Thus, the definite integral (Figure 5):

\displaystyle \int_0^1 \dfrac{e^x-1}{x} dx= \textrm{Ei}(1)-\gamma=1.3179021514544...

This leads us to the formula:

\textrm{Ei}(1)=\displaystyle \gamma + \sum_{n=1}^{\infty} \dfrac{1}{n^2\Gamma(n)} = 1.89511781635...

From this and the above indefinite integral we can obtain the general formula for \textrm{Ei}(x) as:

\textrm{Ei}(x)=\displaystyle \gamma +\log(x) + \sum_{n=1}^{\infty} \dfrac{x^n}{n^2\Gamma(n)}

If we now substitute x by \log(x) we get the series for the logarithmic integral as:

\textrm{Li}(x)=\displaystyle \gamma +\log(\log(x)) + \sum_{n=1}^{\infty} \dfrac{\log^n(x)}{n^2\Gamma(n)}

This was the series for \textrm{Li}(x) that Ramanujan arrived at unaware of work of Gauss, Soldner and their successors in Europe. He then went on to discover other series that converged even faster to \textrm{Li}(x). With these relationships one can finally obtain a relationship between the mysterious Euler-Mascheroni constant \gamma that appears in various formulae pertaining to both the number world and the natural world and the Soldner-Ramanujan constant \mu of number theory. Since \textrm{Ei}(x)=0 when x=\log(\mu) by substituting this into the above series for \textrm{Ei}(x) we get:

\gamma = -\Gamma'(1) =\displaystyle \lim_{n \to \infty}\left( \sum_{k=1}^{n}\dfrac{1}{k} -\log(n) \right) = -\log(\log(\mu)) - \sum_{n=1}^{\infty} \dfrac{\log^n(\mu)}{n^2\Gamma(n)}

The first expression \Gamma'(x) is the derivative of the Gamma function. The second expression is Euler’s original definition of \gamma as a limit. The third is what we obtain from the above substitution, which gives it in relationship to \mu as derived from Ramanujan’s series.

Thus, in the works of the last great mathematicians of the Hindu tradition like Bhāskara-II, Nārāyaṇa and Mādhava we see the preamble to the developments of modern mathematics, which revealed the deep links between the number world and the natural world. Nārāyaṇa’s interest in combinatorics, sequences and sums may be compared with that of Euler. Armed with a photographic memory and an enormous capacity for numerical calculations, Euler was much like a paṇḍita of yore. Indeed, he dealt with infinite sums and definite integrals almost like a continuation of that old tradition. But among the Hindus it was Ramanujan, who close to 600 years after Nārāyaṇa and Mādhava nearly seemed as if he was channeling them to single-handedly take their tradition to a conclusion.

This entry was posted in Heathen thought, History, Scientific ramblings and tagged , , , , , . Bookmark the permalink.