The Narayana Numbers

Contents
Narayana triangle
Meta-Narayana triangle

Narayana Triangle

The narayana numbers are an arrangement of numbers similar to Pascal's triangle that count a sort of permutation:

1 sum: 1 1 1 sum: 2 1 3 1 sum: 5 1 6 6 1 sum: 14 1 10 20 10 1 sum: 42 1 15 50 50 15 1 sum: 132 1 21 105 175 105 21 1 sum: 429 1 28 196 490 490 196 28 1 sum: 1430 1 36 336 1176 1764 1176 336 36 1 sum: 4862 1 45 540 2520 5292 5292 2520 540 45 1 sum: 16796

This triangle is "listed" in the OEIS as sequence A1263; see that entry for some formulas and references. (There are a lot of connections to less well known maths topics.

Here it is easy to recognize the triangular numbers, Sloane's A000217, in the second diagonal. They are a "two-dimensional figurate" sequence, because they count the number of objects in an arragement that is determined by a two-dimensional figure.

The third diagonal (1, 6, 20, 50, 105, 196, ...) is a similar type of sequence describing four-dimensional hyper-pyramid beginning with a square-pyramidal base (Sloane's A002415). In a manner similar to the discussion in my A006542 page, it is made by taking successive sums of another sequence (A000330) which itself is made by taking the sums of yet another sequence (the squares, A000290).

The fourth diagonal (1, 10, 50, 175, 490, 1176, ...) is sequence A006542, which corresponds to a six-dimensional figure like a pyramid starting with a five-sided base. That sequence is described more fully here.

So we have a pattern, going from a triangle to a square to a pentagon, and going from 2 to 4 to 6 dimensions. However, if you check this more closely, you might notice an irregularity: whereas the triangle sequence (1, 3, 6, 10, ...) is adding (2, 3, 4, ...) each time, and the square sequence (1, 4, 9, 16, ...) is adding (3, 5, 7, ...) each time — the pentagon sequence (1, 6, 16, 31, ...) is adding (5, 10, 15, ...) As N is going from 2 to 4 to 6, the N^th-order differences go from 1 to 2 to 5. If the pattern were consistent, it should be something more like (4, 7, 10, ...) (with a second-order difference of 3).

This irregularity becomes a bit more surprising when you look at the next diagonal of the Narayana triangle, (1, 15, 105, 490, 1764, 5292, ...) which turns out to derive from an 8^th-order difference of 14:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 A000217, MCS484 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A000027, MCS220 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A000012 1 6 20 50 105 196 336 540 825 1210 1716 2366 A002415, MCS1725217 1 5 14 30 55 91 140 204 285 385 506 650 A000330, MCS1936 1 4 9 16 25 36 49 64 81 100 121 144 A000290, MCS440 1 3 5 7 9 11 13 15 17 19 21 23 A005408, MCS3538 2 2 2 2 2 2 2 2 2 2 2 A007395 1 10 50 175 490 1176 2520 4950 9075 15730 A006542 1 9 40 125 315 686 1344 2430 4125 6655 A006414 1 8 31 85 190 371 658 1086 1695 2530 A006322 1 7 23 54 105 181 287 428 609 835 A004068, MCS107897 1 6 16 31 51 76 106 141 181 226 A005891, MCS248288 5 10 15 20 25 30 35 40 45 A008587, MCS1767 5 5 5 5 5 5 5 5 A010716 1 15 105 490 1764 5292 13860 32670 70785 143143 273273 A006857 1 14 90 385 1274 3528 8568 18810 38115 72358 130130 A114242 1 13 76 295 889 2254 5040 10242 19305 34243 57772 A114244 1 12 63 219 594 1365 2786 5202 9063 14938 23529 A085463 1 11 51 156 375 771 1421 2416 3861 5875 8591 (none), MCS6990239 1 10 40 105 219 396 650 995 1445 2014 2716 A063490, MCS32147425 9 30 65 114 177 254 345 450 569 702 A005919, MCS113311 21 35 49 63 77 91 105 119 133 A147587 14 14 14 14 14 14 14 14 A010853

The actual pattern here is that the 2N^th-order difference is the N^th Catalan number.

Self-Definition by Symmetry Contraints

Suppose we want to find a minimal set of constraints needed to fix all of the numbers in the Narayana triangls. Michael Somos pointed out¹ to me that the following "axioms" suffice:

The number at the top is 1.
The triangle is bilaterally symmetrical.
The N^th diagonal follows a order 2(N-1) progression (referring to polynomial order, i.e. a constant sequence, a quadratic sequence, a quartic sequence, etc.). (Add as many initial zeros as needed to uniquely determine the sequence)

As it turns out, these three are sufficient, and the 2(N-1)^th-order differences of the N^th diagonal always turn out to be the Catalan numbers as discussed above, which are also the row sums of the N^th rows. One can easily see that a very similar set of axioms defines Pascal's triangle, and suggests extension to higher orders. But the above are not the only set of axioms that work.

Extending the Sequence to Higher-order Triangles

There are at least two ways to go beyond Pascal and Narayana, that are self-consistent and easily estensible. The method used here is probably better known is to compute rows using successive products of fractions of binomial coefficients, the product of fractions method (follow that link for larger tables of the triangles, and links to related OEIS sequences).

The other method uses successive differences and produces triangles that differ starting with the 3^rd (i.e. the first triangle after Narayana); somewhat smaller values and row sums. (Again, follow that link for larger tables of the triangles and links to related OEIS sequences).

The "Meta-Narayana" or Hoggatt Triangle

Named for Verner Hoggatt, who worked out many of its properties in 1977, this triangle is discussed in [2].

This triangle is discussed more fully on my page concerning the Baxter permutations, which are the row sums of the triangle (1, 2, 6, 22, 92, 422, ...; Sloane's sequence A1181).

1 sum: 1 1 1 sum: 2 1 4 1 sum: 6 1 10 10 1 sum: 22 1 20 50 20 1 sum: 92 1 35 175 175 35 1 sum: 422 1 56 490 980 490 56 1 sum: 2074 1 84 1176 4116 4116 1176 84 1 sum: 10754 1 120 2520 14112 24696 14112 2520 120 1 sum: 58202 1 165 4950 41580 116424 116424 41580 4950 165 1 sum: 326240 1 220 9075 108900 457380 731808 457380 108900 9075 220 1 sum: 1882960

To generate a row of this triangle, we need the "tetrahedral" numbers, which also appear in the 2^nd diagonal of this triangle: 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, ... To get the N^th row of the triangle (counting the lone "1" at the top as row 1) we need the first N-1 of these numbers. For example, to get the 7^th row we use the numbers 1, 4, 10, 20, 35, 56. The first number in a row is always 1. Then you iterate the process of multiplying by a tetrahedral number and dividing by another one:

first term: 1
1×56/1 = 56
56×35/4 = 490
490×20/10 = 980
980×10/20 = 490
490×4/35 = 56
56×1/56 = 1

Meta-Meta-Narayana Triangle

Continuing in like manner, more such triangles can be generated. Beyond the natural numbers, triangular numbers, and tetrahedral numbers is the "simplex" or "hyper-tetrahedral" numbers.

The row sums (1, 2, 7, 32, 177, ...) are the Hoggatt sequence (Sloane's A5362).

1 sum: 1 1 1 sum: 2 1 5 1 sum: 7 1 15 15 1 sum: 32 1 35 105 35 1 sum: 177 1 70 490 490 70 1 sum: 1122 1 126 1764 4116 1764 126 1 sum: 7898 1 210 5292 24696 24696 5292 210 1 sum: 60398 1 330 13860 116424 232848 116424 13860 330 1 sum: 494078 1 495 32670 457380 1646568 1646568 457380 32670 495 1 sum: 4274228

To generate a row N of this triangle, we need the first N-1 simplex numbers, which as before are found in the 2^nd diagonal of the triangle: 1, 5, 15, 35, 70, 126, 210, 330, 495, ... For example, to get the 7^th row we use the numbers 1, 5, 15, 35, 70, 126. Once again the first number in a row is always 1. Then you iterate the process of multiplying by a simplex (or hyper-tetrahedral) number and dividing by another one:

first term: 1
1×126/1 = 126
126×70/5 = 1764
1764×35/15 = 4116
4116×15/35 = 1764
1764×5/70 = 126
126×1/126 = 1

References

1 : Michael Somos, personal correspondence, 2022.

[2] Daniel C. Fielder and Cecil O. Alford, "On a conjecture by Hoggatt with extensions to Hoggatt sums and Hoggatt triangles." Fibonacci Quarterly #27(2) pp. 160-168 (1989).

Some other sequences are discussed here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Oct 03.

s.30