Pascal Triangle and Combinatorics
Chapter Twenty-Eight
Syllabus topic Module 1, "Pascal triangle and combinatorics"
Pages 91 to 94 of 378
In one line
The Meru-prastāra is what is now called Pascal's triangle, and its entries are the binomial coefficients, the number of ways of choosing k things from n.
In the wording you can write in an examination: the binomial coefficient, written C(n, k) and read as n choose k, is the number of distinct subsets of size k that can be formed from a set of n distinct elements. It equals n factorial divided by k factorial times n minus k factorial, it satisfies the addition rule that C(n, k) equals C(n minus 1, k) plus C(n minus 1, k minus 1), and the array of its values is Pascal's triangle, which is the Meru-prastāra.
Why the two problems are the same problem
The lagakriyā asks: how many patterns of n syllables have exactly k light ones?
Choosing which syllables are light is choosing a set of k positions out of n. Once you have chosen them, the pattern is determined: those positions are light and the rest are heavy. So there are exactly as many patterns as there are ways of choosing k positions from n.
That is the whole argument, and it is the one to write in an answer. Not a resemblance: a one-to-one correspondence between patterns and subsets.
The closed form, and how to use it without factorials
C(n, k) is n factorial over k factorial times n minus k factorial. Written out for six choose two: 720 over 2 times 24, which is 720 over 48, which is 15.
Do not compute it that way. Factorials get large fast: 20 factorial is already about 2.4 times ten to the eighteenth, while C(20, 2) is only 190. The practical form multiplies and divides alternately.
C(n, k) = (n / 1) ((n-1) / 2) ((n-2) / 3) ... ((n-k+1) / k)
For six choose two that is 6 over 1 times 5 over 2, which is 15, with nothing larger than 30 appearing.
The three routes to the same numbers
GURU, LAGHU = "G", "L"
def prastara(n):
row = [GURU] * n
rows = ["".join(row)]
while GURU in row:
k = row.index(GURU)
row = [GURU] * k + [LAGHU] + row[k + 1:]
rows.append("".join(row))
return rows
def lagakriya(n):
"""Counted off the table: how many patterns have exactly k laghus."""
out = [0] * (n + 1)
for row in prastara(n):
out[row.count(LAGHU)] += 1
return out
def meru(rows):
tri = [[1]]
for _ in range(rows - 1):
prev = tri[-1]
tri.append([1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1])
return tri
def choose(n, k):
num, den = 1, 1
for i in range(k):
num *= n - i
den *= i + 1
return num // den
print("%-4s %-26s %-26s %-6s %s" % ("n", "counted off the table", "Meru row n", "sum", "2**n"))
tri = meru(9)
for n in range(1, 9):
counted = lagakriya(n)
row = tri[n]
print("%-4d %-26s %-26s %-6d %d"
% (n, counted, row, sum(counted), 2 ** n))
print()
print("and the same figures from the binomial coefficient, n = 6")
print(" k: ", " ".join("%3d" % k for k in range(7)))
print(" C(6,k): ", " ".join("%3d" % choose(6, k) for k in range(7)))
print(" Meru: ", " ".join("%3d" % x for x in tri[6]))Pascal Triangle and Combinatorics
n counted off the table Meru row n sum 2**n
1 [1, 1] [1, 1] 2 2
2 [1, 2, 1] [1, 2, 1] 4 4
3 [1, 3, 3, 1] [1, 3, 3, 1] 8 8
4 [1, 4, 6, 4, 1] [1, 4, 6, 4, 1] 16 16
5 [1, 5, 10, 10, 5, 1] [1, 5, 10, 10, 5, 1] 32 32
6 [1, 6, 15, 20, 15, 6, 1] [1, 6, 15, 20, 15, 6, 1] 64 64
7 [1, 7, 21, 35, 35, 21, 7, 1] [1, 7, 21, 35, 35, 21, 7, 1] 128 128
8 [1, 8, 28, 56, 70, 56, 28, 8, 1] [1, 8, 28, 56, 70, 56, 28, 8, 1] 256 256
and the same figures from the binomial coefficient, n = 6
k: 0 1 2 3 4 5 6
C(6,k): 1 6 15 20 15 6 1
Meru: 1 6 15 20 15 6 1Three independent routes: counting the patterns one at a time, adding cells in the staircase, and the closed form. They agree at every value printed, and the first two agree at every n from one to eight, which is 510 patterns counted by hand by the machine.
The identities worth knowing
Each of these is a fact about the triangle that a five-mark question can ask for, and each has a one-line reason.
Symmetry: C(n, k) equals C(n, n minus k). Choosing which k are light is the same as choosing which n minus k are heavy. That is why every row reads the same backwards.
Row sum: the row for n adds to 2 to the power n. Every pattern has some number of light syllables, so summing over all k counts every pattern once. This is the link between the lagakriyā and the saṅkhyā, and it is Halāyudha's own 64 for the gāyatrī.
The ends are one. Exactly one all-heavy pattern and one all-light one.
The second entry is n. There are n positions in which the single light syllable can stand.
The addition rule. Proved in [Meru-Prastāra: Halāyudha's Staircase] by splitting on the last syllable.
Pascal Triangle and Combinatorics
Worked example: a real prosodic question
How many six-syllable patterns have more heavy syllables than light ones?
By the row. More heavy than light means fewer than three light, so k is 0, 1 or 2. The row for six is 1, 6, 15, 20, 15, 6, 1. So 1 plus 6 plus 15, which is 22.
Checked another way. By symmetry, the number with more light than heavy is also 22, and the number with exactly three of each is 20. Now 22 plus 22 plus 20 is 64, which is the whole table. The two answers are consistent.
That second calculation is worth doing every time. A row of the Meru gives you a free check on any counting answer, because the parts must add to the row sum.
What this is NOT
It is not a claim of priority over Pascal. The claim this book makes is that the array and its construction rule are in Halāyudha's commentary, which is a statement about a text. Questions of who first wrote down what, in which century, in which tradition, are a matter for historians of mathematics and the literature on them is large. An answer should say the array is in the commentary and leave the rest.
It is not the same object as the prastāra. Both are called prastāra in Sanskrit, and they are different things: one lists, the other counts.
It is not limited to two symbols. With three symbols the analogous array is the trinomial triangle, and the prosodic tradition that counts by mātrā rather than by syllable meets a related problem.
Quick revision
- The lagakriyā and the count of k-subsets of n are the same problem: choosing which syllables are light is choosing which positions.
- C(n, k) is n factorial over k factorial times n minus k factorial, but compute it by alternating multiplication and division.
- Identities: symmetry, so rows read the same backwards; row sum 2 to the power n; ends are one; second entry is n; and the addition rule.
- Three routes agree: counting off the prastāra, the Meru's additions, the closed form.
- A row gives a free check on any counting answer, since the parts must add to the row sum.
Test yourself
1. Explain in one sentence why the lagakriyā is a binomial coefficient.
Because choosing which k of the n syllables are light is exactly choosing a subset of k positions from n, and the pattern is then determined, so patterns and subsets correspond one to one.
2. Compute C(7, 3) without factorials, showing the steps.
7 over 1 is 7; times 6 over 2 is 21; times 5 over 3 is 35. So C(7, 3) is 35, which is the fourth entry of row seven.
Pascal Triangle and Combinatorics
3. How many eight-syllable patterns have exactly three light syllables, and how do you check your answer?
Row eight is 1, 8, 28, 56, 70, 56, 28, 8, 1, so the answer is 56. Check it by symmetry against the count with five light syllables, which is also 56, and by the row sum, which is 256.
4. State carefully what this book claims about the Meru-prastāra and Pascal's triangle.
That the array, its construction by adding the two cells above, and the reading of its rows as counts of patterns by number of light syllables are all present in Halāyudha's commentary on Piṅgala. It makes no claim about priority, which is a historical question with its own literature.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.