Radio Shack EC-4019: Catalan and Borel Triangles
Introduction: Catalan and Borel Triangles
Catalan numbers counts a number of lattice paths, straight lines with segment of length 1, in the Cartesian plane from the origin (0,0) to the point (n,k). There path does not go above the line y = x.
Entries in Borel's Triangle depend on the entries of Catalan's Triangle. There are various interpretations of how counting relate to Borel's triangle, including counting the number of Dyck path of semi-length n+1, counting path in leaf-market binary trees, and set of binary trees with n+1 vertices with k marked vertices with no markings on the tree's right spine. Please see the source below for more details.
Formula Derivation
You can find any entry in Catalan's triangle by the formula:
C = (n - k + 1) / (n + 1) * COMB(n + k, n)
where:
1. k ≤ n, I do believe that k and n need to be integers, and
2. COMB is the nCr, combination function, where for any x and y:
COMB(x, y) = x! / ( y! * (x - y)! )
We can simplify the formula for Catalan's triangle by:
C
= (n - k + 1) / (n + 1) * COMB(n + k, n)
= (n - k + 1) / (n + 1) * (n + k)! / (n! * (n + k - n)!)
= (n - k + 1) / (n + 1) * (n + k)! / (n! * k!)
= (n - k + 1) / (n + 1) * (n + k)! /n! * 1/k!
Since (n + 1) * n! = (n + 1) * n * (n - 1) * (n - 2) * ... = (n + 1)!
= (n - k + 1) * (n + k)! / ((n + 1)! * (n - k)!)
Observe that
C / (n-k+1) = (n + k)! / ((n + 1)! * (n - k)!)
Similarly, you can find any entry in Borel's triangle by the formula:
B
= 1 / (n + 1) * COMB(2n + 2, n - k) * COMB(n + k, n)
= 1/ (n + 1) * (2n + 2)! / ((n - k)! * (n + 2 + k)!) * (n + k)!/(n! * k!)
= (2n + 2)! / ((n - k)! * (n + 2 + k)!) * (n + k)!/((n+1)! * k!)
= (2n + 2)! / ((n - k)! * (n + k + 2)!) * Ca
Radio Shack EC-4019 Programs: Catalan and Borel Triangle Numbers
To run the program:
1. Store k in memory register 1. Keystrokes: k [ Kin ] [ 1 ]
2. Store n in memory register 2. Keystrokes: n [ Kin ] [ 2 ]
3. To find the Catalan Triangle, run program I.
4. To find the Borel triangle number, run program I, then immediately run program II. Program II depends on the result of program I.
Make sure that k ≤ n, as the programs assume that your inputs are valid.
Program I: Catalan Triangle Number
(25 steps)
(small x: multiply key, slash: divide key)
[(---
Kout 2
-
Kout 1
+
1
---)]
x
[(---
Kout 2
+
Kout 1
---)]
x!
/
[(---
Kout 2
+
1
---)]
x!
/
Kout 1
x!
=
Program II: Borel Triangle Number
(28 steps)
(small x: multiply key, slash: divide key)
x
[(---
2
x
Kout 2
+
2
---)]
x!
/
[(
Kout 2
-
Kout 1
+
1
)]
x!
/
[(
Kout 1
+
Kout 2
+
2
---)]
x!
=
Examples
k = 2, n = 6, Catalan (I): 20, Borel (II): 4004
k = 3, n = 5, Catalan (I): 28, Borel (II): 616
k = 4, n = 4, Catalan (I): 14, Borel (II): 14
Source:
Cai, Yue and Yan, Catherine. "Coutning with Borel's Triangle" Elsevier B.V. Discrete Mathematics. November 15, 2018
https://arxiv.org/pdf/1804.01597.pdf
Also: https://doi.org/10.1016/j.disc.2018.10.031
Retrieved August 9, 2020
Eddie
All original content copyright, © 2011-2020. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.