Extending Pascal and Narayana by Successive Difference Method

The well-known Pascal's triangle and Narayana triangle can be generated by a variety of methods. This page shows a construction suggested to me by Michael Somos¹ based on the fact that the k^th "diagonals" are all polynomials (or degree k or 2k for Pascal and Narayana respectively). After constructing Pascal and Narayana triangles this way, it is clear that the method extends to higher "levels" of triangles.

The Axioms

These are the rules for constructing a triangle of "level" L, where L=1 gives Pascal's triangle and L=2 gives the Narayana triangle:

The topmost element T(0,0) is 1.
The triangle has bilateral symmetry: T(n,k)=T(n,n-k) for all n>0 and k<=n.
The numbers in the k^th diagonal D(k)=T(n,n+k) are the values of some polynomial in x of degree Lk with constant coefficients, for x=k.

Using just these rules there is a single wyay to build a triangle for any natural number L.

Illustration

To illustrate the construction, here we create the Narayana triangle which is level L=2.

Put a 1 at the top: 1 sum: 1

1^st diagonal is an order-0 progression, i.e. a constant sequence, so it is all 1's: 1 sum: 1 1 1 1 1 1

Bilateral symmetry determines the "other" 1^st diagonal and gives us the next row sum: 1 sum: 1 1 1 sum: 2 1 1 1 1 1 1 1 1

2^nd diagonal is an order 2 progression (quadratic progression). We only have one term, but we can add two 0's in front of that to get 0, 0, 1. The method of finite differences determines that the 2^nd-order (2N^th order) difference should be 1. Using this to extend the sequence we get 0, 0, 1, 3, 6, 10, 15, ... 1 sum: 1 1 1 sum: 2 1 3 1 sum: 5 1 6 1 1 10 1 1 15 1

Apply bilateral symmetry, again: 1 sum: 1 1 1 sum: 2 1 3 1 sum: 5 1 6 6 1 sum: 14 1 10 10 1 sum: 42 1 15 15 1 sum: 132

For the 3^rd diagonal we need a 4^th-order progression, so we determine the 4^th differences of 0, 0, 0, 1, 6 (which is 2); and the sequence is continued: 1, 6, 20, 50, 105, 196, ... then construction continues as above.

The 1^st triangle in the series is Pascal's triangle. It has diagonals that are k-degree polynomials for all natural numbers k.

Pascal's triangle (L=1)

														1															1
													1		1														2
												1		2		1													4
											1		3		3		1												8
										1		4		6		4		1											16
									1		5		10		10		5		1										32
								1		6		15		20		15		6		1									64
							1		7		21		35		35		21		7		1								128
						1		8		28		56		70		56		28		8		1							256
					1		9		36		84		126		126		84		36		9		1						512
				1		10		45		120		210		252		210		120		45		10		1					1024
			1		11		55		165		330		462		462		330		165		55		11		1				2048
		1		12		66		220		495		792		924		792		495		220		66		12		1			4096
	1		13		78		286		715		1287		1716		1716		1287		715		286		78		13		1		8192
1		14		91		364		1001		2002		3003		3432		3003		2002		1001		364		91		14		1	16384

Diagonals:

T(n+0,0) = 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A0012

T(n+1,1) = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ... A0027

T(n+2,2) = 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, ... A0217

T(n+3,3) = 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, ... A0292

T(n+4,4) = 1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, ... A0332

T(n+5,5) = 1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568, 11628, 15504, 20349, 26334, 33649, 42504, ... A0389

T(n+6,6) = 1, 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, 18564, 27132, 38760, 54264, 74613, 100947, 134596, 177100, ... A0579

T(n+7,7) = 1, 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, 31824, 50388, 77520, 116280, 170544, 245157, 346104, 480700, 657800, ... A0580

T(n+8,8) = 1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 43758, 75582, 125970, 203490, 319770, 490314, 735471, 1081575, 1562275, 2220075, ... A0581

T(n+9,9) = 1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92378, 167960, 293930, 497420, 817190, 1307504, 2042975, 3124550, 4686825, 6906900, ... A0582

Row sums: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, ... A0079 (the powers of 2)

The 2^nd triangle in the series is the Narayana triangle. It has diagonals that are 2k-degree polynomials.

Narayana triangle (L=2)

														1															1
													1		1														2
												1		3		1													5
											1		6		6		1												14
										1		10		20		10		1											42
									1		15		50		50		15		1										132
								1		21		105		175		105		21		1									429
							1		28		196		490		490		196		28		1								1430
						1		36		336		1176		1764		1176		336		36		1							4862
					1		45		540		2520		5292		5292		2520		540		45		1						16796
				1		55		825		4950		13860		19404		13860		4950		825		55		1					58786
			1		66		1210		9075		32670		60984		60984		32670		9075		1210		66		1				208012
		1		78		1716		15730		70785		169884		226512		169884		70785		15730		1716		78		1			742900
	1		91		2366		26026		143143		429429		736164		736164		429429		143143		26026		2366		91		1		2674440
1		105		3185		41405		273273		1002001		2147145		2760615		2147145		1002001		273273		41405		3185		105		1	9694845

Diagonals:

T(n+0,0) = 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A0012

T(n+1,1) = 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, ... A0217

T(n+2,2) = 1, 6, 20, 50, 105, 196, 336, 540, 825, 1210, 1716, 2366, 3185, 4200, 5440, 6936, 8721, 10830, 13300, 16170, ... A2415

T(n+3,3) = 1, 10, 50, 175, 490, 1176, 2520, 4950, 9075, 15730, 26026, 41405, 63700, 95200, 138720, 197676, 276165, 379050, 512050, 681835, ... A6542

T(n+4,4) = 1, 15, 105, 490, 1764, 5292, 13860, 32670, 70785, 143143, 273273, 496860, 866320, 1456560, 2372112, 3755844, 5799465, 8756055, 12954865, 18818646, ... A6857

T(n+5,5) = 1, 21, 196, 1176, 5292, 19404, 60984, 169884, 429429, 1002001, 2186184, 4504864, 8836464, 16604784, 30046752, 52581816, 89311761, 147685461, 238369516, 376372920, ... A108679

T(n+6,6) = 1, 28, 336, 2520, 13860, 60984, 226512, 736164, 2147145, 5725720, 14158144, 32821152, 71954064, 150233760, 300467520, 578399976, 1075994073, 1941008916, 3405278800, 5824819000, ... A134288

T(n+7,7) = 1, 36, 540, 4950, 32670, 169884, 736164, 2760615, 9202050, 27810640, 77364144, 200443464, 488259720, 1126753200, 2478857040, 5226256926, 10606227291, 20796524100, 39525557500, 73018266750, ... A134289

T(n+8,8) = 1, 45, 825, 9075, 70785, 429429, 2147145, 9202050, 34763300, 118195220, 367479684, 1057896060, 2848181700, 7229999700, 17420856420, 40067969766, 88385227425, 187746398125, 385374185625, 766691800875, ... A134290

T(n+9,9) = 1, 55, 1210, 15730, 143143, 1002001, 5725720, 27810640, 118195220, 449141836, 1551580888, 4936848280, 14620666060, 40648664980, 106847919376, 267119798440, 638337753625, 1464421905375, 3237143159250, 6917263803450, ... A134291

Row sums: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ... A0108 (Catalan numbers)

The 3^rd triangle in the series has diagonals that are 3k-degree polynomials.

3^rd triangle (L=3)

														1															1
													1		1														2
												1		4		1													6
											1		10		10		1												22
										1		20		49		20		1											91
									1		35		168		168		35		1										408
								1		56		462		900		462		56		1									1938
							1		84		1092		3630		3630		1092		84		1								9614
						1		120		2310		12012		20449		12012		2310		120		1							49335
					1		165		4488		34320		91091		91091		34320		4488		165		1						260130
				1		220		8151		87516		340340		529984		340340		87516		8151		220		1					1402440
			1		286		14014		203775		1108536		2524704		2524704		1108536		203775		14014		286		1				7702632
		1		364		23023		440440		3233230		10279152		15023376		10279152		3233230		440440		23023		364		1			42975796
	1		455		36400		894608		8610602		36858822		75116880		75116880		36858822		8610602		894608		36400		455		1		243035536
1		560		55692		1723800		21246940		118982864		326058810		454457124		326058810		118982864		21246940		1723800		55692		560		1	1390594458

Diagonals:

T(n+0,0) = 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A0012

T(n+1,1) = 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, ... A0292

T(n+2,2) = 1, 10, 49, 168, 462, 1092, 2310, 4488, 8151, 14014, 23023, 36400, 55692, 82824, 120156, 170544, 237405, 324786, 437437, 580888, ... A51947

T(n+3,3) = 1, 20, 168, 900, 3630, 12012, 34320, 87516, 203775, 440440, 894608, 1723800, 3174444, 5620200, 9612480, 15945864, 25741485, 40551852, 62491000, 94394300, ... (not in OEIS)

T(n+4,4) = 1, 35, 462, 3630, 20449, 91091, 340340, 1108536, 3233230, 8610602, 21246940, 49128300, 107402022, 223590290, 445858864, 855761368, 1587391575, 2855526245, 4996155450, 8523805290, ... (not in OEIS)

T(n+5,5) = 1, 56, 1092, 12012, 91091, 529984, 2524704, 10279152, 36858822, 118982864, 351540280, 962914680, 2470246506, 5984089216, 13781092160, 30340630320, 64159481295, 130835020680, 258164977980, 494380706820, ...

T(n+6,6) = 1, 84, 2310, 34320, 340340, 2524704, 15023376, 75116880, 326058810, 1258472600, 4398116580, 14115694320, 42075627300, 117544609600, 310074573600, 777186915120, 1860624957555, 4273704384300, 9454228451850, 20209848674400, ...

T(n+7,7) = 1, 120, 4488, 87516, 1108536, 10279152, 75116880, 454457124, 2356939398, 10750951640, 43981165800, 163842880500, 562611245040, 1798432526880, 5395297580640, 15293928222540, 41199552631575, 105987868730640, 261476946896880, 620875422489960, ...

T(n+8,8) = 1, 165, 8151, 203775, 3233230, 36858822, 326058810, 2356939398, 14442030625, 77074837125, 365755136175, 1568554635375, 6158386814580, 22370208514500, 75838312806300, 241704042105240, 728666597523150, 2088844246233030, 5719808213369250, ...

T(n+9,9) = 1, 220, 14014, 440440, 8610602, 118982864, 1258472600, 10750951640, 77074837125, 477052676100, 2605203250650, 12768585102000, 56938067566380, 233592072067200, 889836203593920, 3171835499907360, ...

Row sums: 1, 2, 6, 22, 91, 408, 1938, 9614, 49335, 260130, 1402440, 7702632, 42975796, 243035536, 1390594458, ... A0139 2(3n)!/((2n+1)! ((n+1)!)).

The 4^th triangle in the series has diagonals that are 4k-degree polynomials.

4^th triangle (L=4)

														1															1
													1		1														2
												1		5		1													7
											1		15		15		1												32
										1		35		99		35		1											171
									1		70		435		435		70		1										1012
								1		126		1485		3211		1485		126		1									6435
							1		210		4257		17108		17108		4257		210		1								43152
						1		330		10725		72618		134096		72618		10725		330		1							301444
					1		495		24453		260260		802332		802332		260260		24453		495		1						2175082
				1		715		51480		817700		3922512		6527241		3922512		817700		51480		715		1					16112057
			1		1001		101530		2311218		16376100		42195846		42195846		16376100		2311218		101530		1001		1				121971392
		1		1365		189618		5987774		60192342		227779695		352049500		227779695		60192342		5987774		189618		1365		1			940351090
	1		1820		338130		14419366		199138544		1062669069		2405081250		2405081250		1062669069		199138544		14419366		338130		1820		1		7363296360
1		2380		579462		32626230		602922782		4393021160		13970931975		20434596975		13970931975		4393021160		602922782		32626230		579462		2380		1	58434764955

Diagonals:

T(n+0,0) = 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A0012

T(n+1,1) = 1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, ... A0332

T(n+2,2) = 1, 15, 99, 435, 1485, 4257, 10725, 24453, 51480, 101530, 189618, 338130, 579462, 959310, 1540710, 2408934, 3677355, 5494401, 8051725, 11593725, ... A34266

T(n+3,3) = 1, 35, 435, 3211, 17108, 72618, 260260, 817700, 2311218, 5987774, 14419366, 32626230, 69955340, 143112256, 280905348, 531470660, 973013275, 1729438425, 2992665585, 5053935705, ... (not in OEIS)

T(n+4,4) = 1, 70, 1485, 17108, 134096, 802332, 3922512, 16376100, 60192342, 199138544, 602922782, 1692118188, 4446999400, 11033699380, 26019626760, 58643783100, 126915215895, 264789028350, 534389931435, 1046321539320, ... (not in OEIS)

T(n+5,5) = 1, 126, 4257, 72618, 802332, 6527241, 42195846, 227779695, 1062669069, 4393021160, 16397325945, 56072151720, 177702418530, 526811604165, 1472149666980, 3902514432075, 9866381025150, 23898461299020, 55677381158190, 125185568743620, ...

T(n+6,6) = 1, 210, 10725, 260260, 3922512, 42195846, 352049500, 2405081250, 13970931975, 70926758760, 321271345395, 1319417078850, 4975909711500, 17410749424200, 57002548790880, 175859882398200, 514301939558550, 1433009239546500, 3820771261215150, 9785067659025120, ...

T(n+7,7) = 1, 330, 24453, 817700, 16376100, 227779695, 2405081250, 20434596975, 145499643900, 894293914800, 4852182247380, 23647178950200, 104955225512280, 429010372187100, 1629921221334000, 5800077948401100, ...

T(n+8,8) = 1, 495, 51480, 2311218, 60192342, 1062669069, 13970931975, 145499643900, 1253306385936, 9215354832816, 59236848763092, 339124799662740, 1754807980062060, 8306203442095944, ...

T(n+9,9) = 1, 715, 101530, 5987774, 199138544, 4393021160, 70926758760, 894293914800, 9215354832816, 80233646275024, 605290860465148, 4035186628845892, ...

Row sums: 1, 2, 7, 32, 171, 1012, 6435, 43152, 301444, 2175082, 16112057, 121971392, 940351090, 7363296360, 58434764955, ... naratest3(5) (not in OEIS)

The 5^th triangle in the series has diagonals that are 5k-degree polynomials.

5^th triangle (L=5)

														1															1
													1		1														2
												1		6		1													8
											1		21		21		1												44
										1		56		176		56		1											290
									1		126		946		946		126		1										2146
								1		252		3861		8976		3861		252		1									17204
							1		462		13013		59636		59636		13013		462		1								146224
						1		792		38038		309264		603141		309264		38038		792		1							1299331
					1		1287		99528		1333344		4543770		4543770		1333344		99528		1287		1						11955860
				1		2002		238238		4976784		27477065		47759400		27477065		4976784		238238		2002		1					113147580
			1		3003		529958		16536954		139929240		390907530		390907530		139929240		16536954		529958		3003		1				1095813372
		1		4368		1108536		49912544		620213055		2630730960		4215576416		2630730960		620213055		49912544		1108536		4368		1			10819515344
	1		6188		2200276		138922300		2450206330		15110742465		36592148032		36592148032		15110742465		2450206330		138922300		2200276		6188		1		108588451184
1		8568		4173806		360752240		8783060715		76105012620		266427183308		401881092624		266427183308		76105012620		8783060715		360752240		4173806		8568		1	1105241475140

Diagonals:

T(n+0,0) = 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A0012

T(n+1,1) = 1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568, 11628, 15504, 20349, 26334, 33649, 42504, ... A0389

T(n+2,2) = 1, 21, 176, 946, 3861, 13013, 38038, 99528, 238238, 529958, 1108536, 2200276, 4173806, 7610526, 13401916, 22881320, 37999335, 61553635, 97485960, 151261110, ... (not in OEIS)

T(n+3,3) = 1, 56, 946, 8976, 59636, 309264, 1333344, 4976784, 16536954, 49912544, 138922300, 360752240, 882119460, 2046243760, 4530501360, 9622635120, 19690230195, 38957308920, 74757900270, 139515162720, ... (not in OEIS)

T(n+4,4) = 1, 126, 3861, 59636, 603141, 4543770, 27477065, 139929240, 620213055, 2450206330, 8783060715, 28964147940, 88835825715, 255655343790, 695346729615, 1798214177760, 4444025522310, 10540981176660, 24086030016510, 53189272465560, ...

T(n+5,5) = 1, 252, 13013, 309264, 4543770, 47759400, 390907530, 2630730960, 15110742465, 76105012620, 342959163885, 1404627806400, 5293511182440, 18540873442080, 60853318162920, 188440578406080, 553736735982990, 1551684722373000, 4163983037123910, ...

T(n+6,6) = 1, 462, 38038, 1333344, 27477065, 390907530, 4215576416, 36592148032, 266427183308, 1676343486664, 9320576087064, 46592467821760, 212284800359676, 891349897080632, 3480512936547408, ...

T(n+7,7) = 1, 792, 99528, 4976784, 139929240, 2630730960, 36592148032, 401881092624, 3644482260276, 28186422600688, 190476539428032, 1145991630572880, 6230272847435208, ...

T(n+8,8) = 1, 1287, 238238, 16536954, 620213055, 15110742465, 266427183308, 3644482260276, 40575409433689, 380628511630367, 3087744281888994, ...

T(n+9,9) = 1, 2002, 529958, 49912544, 2450206330, 76105012620, 1676343486664, 28186422600688, 380628511630367, 4282614695229046, ...

Row sums: 1, 2, 8, 44, 290, 2146, 17204, 146224, 1299331, 11955860, 113147580, 1095813372, 10819515344, 108588451184, 1105241475140, ... (not in OEIS)

References

1 : Michael Somos, personal correspondence, 2022.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2022 Sep 18.

s.30