Saturday, August 29, 2020

Radio Shack EC-4019: Catalan and Borel Triangles

 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:

= (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:


= 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

+


---)]

[(---

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

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.