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:

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. 

Fun with Radio Shack EC-4019 and Casio fx-3800P

Fun with Radio Shack EC-4019 and Casio fx-3800P

First blog entry of the 10th year of this blog (4/11/2020 - 4/11/2021).  I can't expression enough gratitude for your support and comments - Eddie

Sums

n
∑ x  = (n^2 + n) / 2
x = 1

Program (9 steps):

ENT
Kin 1
x^2 
+
Kout 1
=
÷ 
2 
= 

Execution:  [ # ] n [ RUN ]

where [ # ] represents program keys [ I ], [ II ], [ III ], and [ IV ] in RUN mode ( [ MODE ] [ . ] )

Example:  n = 48, Result:  1176

n
∑ x^2 = n * ((n/3 + 1/2) * n + 1/6 )
x=1

Program (16 steps):

ENT
Kin 1
*
(
Kout 1
x^2
÷ 
3
+
Kout 1
÷
2 
+
6
1/x
=

Execution:  [ # ] n [ RUN ]

Example:  n = 48, Result:  38024

Horner's Rule:  Cubic Polynomials

Calculate p(x) by Horner's Rule where:

p(x) = a*x^3 + b*x^2 + c*x + d = x * ( x * ( a*x + b ) + c ) + d

Program (16 steps):

Kout 5
+
Kout 1
*
(
Kout 4
+ 
Kout 1
* 
(
Kout 2
*
Kout 1
+ 
Kout 3
=

Execution:  x [ Kin ] 1, a [ Kin ] 2, b [ Kin ] 3, c [ Kin ] 4, d [ Kin ] 5.   Press [ # ]

Example:  x = K1 = 50, a = K2 = 1, b = K3 = 4, c = K4 = 5, d = K5 = -200
Result:  135,050

Head Winds And Cross Winds

Head Winds:
HW = K * cos(D - HDG - V)

Cross Winds:
RCW = K * sin(D - HDG - V)

where:
K = wind velocity (mi/hr)  (K1)
D = wind direction with 0° due North, clockwise (degrees)  (K2)
HDG = airplane direction with 0° due North, clockwise (degrees)  (K3)
V = compass adjustment   (K4)

Mode 4: Degrees

Program (13 steps):

Mode
4        //  Degree mode
Kout 1
P → R 
(
Kout 2 
-
Kout 3
-
Kout 4
= 
HLT   // HW
X ←→ Y  // RCW

Execution:
K [ Kin ] 1,  D [ Kin ] 2,  HDG [ Kin ] 3,  V [ Kin ] 4.  Press [ # ].

Example:
K = 25 mi/hr = K1
D = 240° = K2
HDG = 280°  = K3
V = 0  = K4

Results:
HW:  19.15111108 mi/hr
RCW:  -16.09699024 mi/hr

Source:  HP 65 Aviation Pac-1 Hewlett Packard.  1974

Rate of Climb

Rate of Climb (ft/min):
ROC = TAS * ALT ÷ √( DIST^2 + ALT^2 )

where:
TAS = true airplane speed (ft/min)   (K1)
ALT = vertical distance (ft)   (K2)
DIST = horizontal distance (ft)   (K3)

Conversion factors:
1 knot = 101.269 ft/min
1 nautical mile = 6072.12 ft

Program (13 steps):

Kout 1
*
Kout 2
÷
(
Kout 2
x^2
+ 
Kout 3
x^2
)
√
=

Execution:
TAS [ Kin ] 1,  ALT [ Kin ] 2,  DIST [ Kin ] 3.  Press [ # ].

Example:
TAS = 4,300 ft/min = K1
ALT = 3,000 ft = K2
DIST = 81,425 ft = K3

Result:  ROC: 158.3205808 ft/min

Source:  HP 65 Aviation Pac-1 Hewlett Packard.  1974

Modulus

For positive integers N, M:
N mod M = ( N / M - int(N / M) ) * M

Results lie in the interval [ -int( M / 2 ), int( M / 2 ) ]

Program (16 steps):

MODE
7
0     // Fix 0 mode 
Kout 2
1/x
*
Kout 1
= 
Kin 3
- 
Kout 3
RND   // round displayed number to settings
=
*
Kout 2
=

Execution:
N [ Kin ] 1,  M  [ Kin ] 2.  Press [ # ].

Examples:

48 mod 17 = -3  (equivalent to 48 mod 17 = 14)

721 mod 21 = 7


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.