Last fall, I learned the names of Pingala and Hemachandra from a blog post by James Propp. Both have been described as poets and mathematicians, and both produced works related to what are commonly known as the Fibonacci sequence \[ 1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\dots\text. \] Pingala lived around the 3rd century BCE, and Hemachandra lived in the 12th century CE. (The book Liber abaci—which contains the rabbit problem that associated Fibonacci’s name with the above sequence, along with other, more useful ideas—was produced later, in 1202.) In between them came Virahanka, sometime between the 6th and 8th centuries CE; following Manjul Bhargava, it is Virahanka’s name I will emphasize in this post.
In Sanskrit poetry, each syllable is either short or long, lasting one or two beats. Some forms of poetic meter have a fixed number of syllables in each line, and some have a fixed number of beats in each line. In the latter case, a natural question (asked at least as early as Pingala) is: how many ways can a line of $n$ beats be metrically divided into short and long syllables? For example, a line with three beats could be arranged “short, short, short” or “long, short” or “short, long”. This corresponds to the equalities $3 = 1+1+1 = 2+1 = 1+2$.
Virahanka seems to have been the first to provide a complete answer, stating that each line of $n$ beats must end with either a short syllable or a long syllable; therefore, the number of possibilities equals the sum of the numbers of possibilities for a line with $n-1$ beats and a line with $n-2$ beats. Because a line with one beat can be divided in only one way, and a line with two beats can be divided in two ways (“short, short” or “long”), the resulting sequence is the same as Fibonacci’s rabbit-counting sequence.1 (The additional initial $1$ in the sequence above will be accounted for momentarily.)
Not only does poetic meter provide a more natural setting for this counting problem than rabbits, it is more reasonably generalized. Suppose, for instance, that instead of just two lengths of syllables, we had a language with three lengths of syllables: one beat, two beats, and three beats. Now how many metrical ways are there to compose a poetic line of $n$ beats? As before, we can work out the first few cases by hand: $1 = 1$, $2 = 1 + 1 = 2$, $3 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 3$. For larger numbers of beats, as before we can sort by the length of the final syllable ($1$, $2$, or $3$), and then count how many ways there are to complete the line, using our knowledge of previous line lengths. For example, a line with four beats can be divided in seven ways, four that end with a $1$-beat syllable, two that end with a $2$-beat syllable, and one that ends with a $3$-beat syllable: \[ \begin{array}{rl} 4 &= 1 + 1 + 1 + \boxed{1} = 2 + 1 + \boxed{1} = 1 + 2 + \boxed{1} = 3 + \boxed{1} \\ &= 1 + 1 + \boxed{2} = 2 + \boxed{2} \\ &= 1 + \boxed{3}\text. \end{array} \] In this sequence, each term is therefore the sum of the previous three terms: \[ 1,\;2,\;4,\;7,\;13,\;24,\;44,\;81,\;149,\;274,\;504,\;\dots\text. \] (Has anyone seen a biological application of this sequence, even an implausible one?)2
Generalizing further, suppose we have syllables of lengths $1$, $2$, …, $m$, and we wish to count the number of rhythmic ways to compose a line of $n$ beats. Or put another way, how many sums with terms between $1$ and $m$ add up to $n$?3 A sum of positive integers equalling $n$ is called a composition of $n$. Let $V_{m,n}$ be the number of compositions of $n$ whose largest term is no greater than $m$. I will call $V_{m,1},V_{m,2},V_{m,3},\dots$ the $m$th Virahanka sequence, so that $V_{2,n}$ is the usual $n$th Fibonacci number. By the same reasoning as in the case of $V_{2,n}$, we have \[ V_{m,n} = V_{m,n-1} + V_{m,n-2} + \cdots + V_{m,n-m}, \qquad n > m. \]
We can naturally extend $V_{m,n}$ to be defined when $m$ or $n$ equals $0$, or both. Using the convention that the “empty sum” having no terms is equal to $0$, we get $V_{m,0} = 1$ for all $m$, and $V_{0,n} = 0$ for $n \ge 1$. We can even set $V_{m,n} = 0$ when $n < 0$, which allows us to drop the $n > m$ restriction entirely in the recursive formula above.
Interesting patterns4 emerge when we arrange the numbers $V_{m,n}$ in a single table:
\[ \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 2 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 \\ \hline 3 & 1 & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274 \\ \hline 4 & 1 & 1 & 2 & 4 & 8 & 15 & 29 & 56 & 108 & 208 & 401 \\ \hline 5 & 1 & 1 & 2 & 4 & 8 & 16 & 31 & 61 & 120 & 236 & 464 \\ \hline 6 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 63 & 125 & 248 & 492 \\ \hline 7 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 127 & 253 & 504 \\ \hline 8 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 255 & 509 \\ \hline 9 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 511 \\ \hline 10 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 \end{array} \]Looking along and below the diagonal, for instance, we see that $V_{m,n} = 2^{n-1}$ if $1 \le n \le m$, and also $V_{n-1,n} = 2^{n-1} - 1$. These values make sense if we imagine $n$ beats in a poetic line, which may be grouped up into syllables of lengths $1$, $2$, …, $m$. If $m \ge n$, then any grouping is allowed, and so we just need to decide at which of the $n-1$ spaces between beats to break the syllables, yielding $2^{n-1}$ possibilities. Likewise, if $m = n-1$, then the only grouping that is not allowed is to put all the beats into a single syllable. (These values also follow from the recursive equation for $V_{m,n}$, using the formula for summing geometric series: $1 + 2 + \cdots + 2^{n-1} = 2^n - 1$.)
What happens if we disregard the order of terms in the sum? Or said another way, what if each syllable in a line of poetry must be no longer than the previous one (that is, since order doesn’t matter, we always sort the syllables from largest to smallest)? These correspond to sums in which the terms are non-increasing. Let us call the number of such sums equalling $n$ with no terms larger than $m$ the unordered Virahanka number $U_{m,n}$. For example, \[ \begin{array}{ll} 6 &= 1 + 1 + 1 + 1 + 1 + 1 \\ &= 2 + 2 + 2 = 2 + 2 + 1 + 1 = 2 + 1 + 1 + 1 + 1 \\ &= 3 + 3 = 3 + 2 + 1 = 3 + 1 + 1 + 1 \end{array} \] and so $U_{3,6} = 7$. Here is the table of unordered Virahanka numbers:
\[ \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 2 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 \\ \hline 3 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 8 & 10 & 12 & 14 \\ \hline 4 & 1 & 1 & 2 & 3 & 5 & 6 & 9 & 11 & 15 & 18 & 23 \\ \hline 5 & 1 & 1 & 2 & 3 & 5 & 7 & 10 & 13 & 18 & 23 & 30 \\ \hline 6 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 14 & 20 & 26 & 35 \\ \hline 7 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 21 & 28 & 38 \\ \hline 8 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 29 & 40 \\ \hline 9 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 41 \\ \hline 10 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 \end{array} \]Again the entries stabilize below the diagonal. The entries $U_{n,n}$ are generally called the number of partitions of $n$. Correspondingly, the remaining values of $U_{m,n}$ count the number of partitions of $n$ with no part greater than $m$, which is why $U_{m,n} = U_{n,n}$ if $m \ge n$. By considering partitions whose largest part is $k$, with $k = 1, \dots, m$, we get a recursive formula for these numbers, as well: \[ U_{m,n} = U_{1,n-1} + U_{2,n-2} + \cdots + U_{m,n-m}. \] Unlike the case of $V_{m,n}$, which can be calculated using only earlier terms in the $m$th (ordered) Virahanka sequence, determining $U_{m,n}$ recursively requires knowing entries from all previous rows.
There is a nice visualization that expresses the relationship between the unordered Virahanka numbers $U_{m,n}$ and the ordered Virahanka numbers $V_{m,n}$. A partition is determined by the number of times each integer appears. So we can think of $U_{m,n}$ as counting the number of integer points $(i_1,\dots,i_m)$ such that $i_k \ge 0$ for all $1\le k\le m$ and $\sum\nolimits_{k=1}^m ki_k = n$. This last condition defines a hyperplane orthogonal to $(1,2,\dots,m)$.
If $m = 2$, for each $n$ we count the number of integer points on the line $x + 2y = n$ in the first quadrant (including the origin and the positive $x$- and $y$- axes).
In the case $m = 3$, $U_{3,n}$ counts the number of integer points in the positive octant such that $x + 2y + 3z = n$. The image below shows the 10 points corresponding to partitions of $n = 8$.
Now we need to convert partitions to compositions. A partition in which $k$ appears $i_k$ times corresponds to the $m$-tuple $(i_1,\dots,i_m)$. A composition with the same number of appearances of each $k$ can be obtained by placing the terms of the partition in any order; the number of distinguishable ways of arranging these terms is given by the multinomial coefficient \[ \binom{i_1+\cdots+i_m}{i_1,\dots,i_m} = \frac{(i_1+\cdots+i_m)!}{i_1!\cdots i_m!}\text. \] For example, the partition $8 = 3 + 2 + 2 + 1$ can be arranged into $\binom{1+2+1}{1,2,1} = \frac{4!}{1!2!1!} = 12$ different compositions, first by choosing the position of the $1$, then the positions of the two $2$s, and then placing $3$ in the remaining spot: \[ \begin{array}{rl} 8 &= 3 + 2 + 2 + 1 = 2 + 3 + 2 + 1 = 2 + 2 + 3 + 1 \\ &= 3 + 2 + 1 + 2 = 2 + 3 + 1 + 2 = 2 + 2 + 1 + 3 \\ &= 3 + 1 + 2 + 2 = 2 + 1 + 3 + 2 = 2 + 1 + 2 + 3 \\ &= 1 + 3 + 2 + 2 = 1 + 2 + 3 + 2 = 1 + 2 + 2 + 3 \end{array} \] Thus if we think of each point $(i_1,\dots,i_m)$ as being weighted by this corresponding multinomial coefficient, we can write $V_{m,n}$ as a sum having $U_{m,n}$ terms, as follows: \[ V_{m,n} = \sum_{(i_1,\dots,i_m):\sum ki_k = n} \binom{i_1+\cdots+i_m}{i_1,\dots,i_m}\text. \] When $m = 2$, we have $i_1 + 2i_2 = n$, so $i_1 + i_2 = n - i_2$ and $i_1 = n - 2i_2$, and by setting $j = i_2$ we get the following expression of $V_{2,n}$ (remember, these are the usual Fibonacci numbers) as a sum of binomial coefficients: \[ V_{2,n} = \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n - j}{n - 2j} = \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n - j}{j}\text. \] The binomial coefficients are, of course, the entries in what is commonly known as Pascal’s triangle. But this also was known to Indian scholars, possibly even Pingala: a later commentator, Halayudha (10th century CE), explicitly arranged the same numbers into a triangle, under the name of Meru Prastaara5, and clarified Pingala’s references to them in relation to poetic meter.
When $m = 3$, the formula is a little more elaborate, so let's first look at an example. We have seen that there are seven partitions of $6$ that have no part greater than $3$, corresponding to the triples $(i_1,i_2,i_3) = (6,0,0)$, $(4,1,0)$, $(2,2,0)$, $(0,3,0)$, $(3,0,1)$, $(1,1,1)$, and $(0,0,2)$. (Remember that these are the triples of positive integers such that $i_1 + 2i_2 + 3i_3 = 6$.) The resulting sum in terms of multinomial coefficients is \[ \begin{array}{rl} V_{3,6} &= \displaystyle\binom{6}{6,0,0} + \binom{5}{4,1,0} + \binom{4}{2,2,0} + \binom{3}{0,3,0} + \binom{4}{3,0,1} + \binom{3}{1,1,1} + \binom{2}{0,0,2} \\ &= 1 + 5 + 6 + 1 + 4 + 6 + 1 = 24 \end{array} \] Now for the general sum6: setting $j = i_2$ and $k = i_3$, we have \[ V_{3,n} = \sum_{k=0}^{\lfloor n/3 \rfloor} \sum_{j=0}^{\lfloor (n-3k)/2 \rfloor} \binom{(n-2j-3k)+j+k}{n-2j-3k,j,k} = \sum_{k=0}^{\lfloor n/3 \rfloor} \sum_{j=0}^{\lfloor (n-3k)/2 \rfloor} \binom{n-j-2k}{n-2j-3k,j,k}\text. \]
I’m sure there is much more depth to be explored regarding these numbers, probably all of it known to combinatorialists, but I have to pause here! I hope to post a part 2 soon.
Footnotes:
1. I first learned about a similar way of obtaining the Virahanka–Fibonacci sequence from the book Proofs that Really Count by Arthur Benjamin and Jennifer Quinn. In that text, the problem is to count the number of ways to tile an $n\times1$ grid using $1\times1$ and $2\times1$ pieces, called squares and dominoes. Then they use this visual presentation to prove several common identities involving terms of the sequence.↩2. Some sources, including the OEIS, call numbers in this sequence “Tribonacci numbers.” Cute, but nonsensical, given that the “fi-” prefix refers to the “son” of Bonacci, not to any counting procedure. However, the OEIS does attribute the coining of “tribonacci” to Mark Feinberg in 1963, when he was a 9th grader, and that is honestly a high pedigree—how often does a 14-year-old get to invent a mathematical term that endures for over half a century?↩
3. Exactly this kind of generalization seems to have been considered by the 14th century mathematician Narayana Pandita. It might therefore be reasonable to name the resulting sequences “Virahanka–Narayana” sequences. See “The So-called Fibonacci Numbers in Ancient and Medieval India” by Parmanand Singh and “Nārāyana’s Generalisation of Mātrā-vrtta-prastāra and the Generalised Virahānka-Fibonacci Representation of Numbers” by Raja Sridharan, R Sridharan and M D Srinivas.↩
4. Hopefully I’ll write more about these patterns soon in a followup post.↩
5. According to P. Singh in “The So-called Fibonacci Numbers in Ancient and Medieval India”, “meru is the name of the imaginary mountain that is supposed to stand at the center of the earth.”↩
6. At least a version of this sum was known to Narayana Pandita. He derived the multinomial coefficients through something called a “needle sequence” or “arrow-head” sequence, which I have not yet fully understood. See the references in Footnote 3.↩
No comments:
Post a Comment