Catalan Numbers for the HP-41
Overview
1°) Catalan Numbers
a) Integer Arguments
b) Real Arguments
2°) Generalized Catalan Numbers
a) Program#1
b) Program#2
c) Another Definition
3°) Super-Catalan Numbers
a) Program#1
b) Program#2
c) Program#3
4°) Super-Catalan Numbers of order
m
1°) Catalan Numbers
a) Integer Arguments
-The Catalan numbers are defined by Cn = (2n)!
/ [ n! (n+1)! ] = [1/(n+1)] Cn2n
where Ckn = n! / [ k! (n-k)!
]
-So, they could be calculated via a binomial-coefficient-program, but
the following routine computes them more directly.
-The first few are 1 1 2 5 14
42 132 429 .....................
Data Registers: /
Flags: /
Subroutines: /
| 01 LBL "CAT"
02 ENTER^ 03 ENTER^ 04 ST+ Y 05 1 06 + 07 1/X 08 LBL 01 09 RCL Y 10 * 11 R^ 12 DSE Z 13 / 14 DSE Z 15 GTO 01 16 X=0? 17 SIGN 18 END |
( 31 bytes / SIZE 000 )
| STACK | INPUTS | OUTPUTS |
| Y | / | n |
| X | n | Cn |
Examples:
10 XEQ "CAT" >>>> C10
= 16796
---Execution time = 3s---
84 R/S
>>>> C84 = 2.705574509 1047
---Execution time = 25s---
172 R/S
>>>> C172 = 8.904665844 1099
---Execution time = 52s---
Note:
-You could add .1 + INT after line 17
to eliminate small roundoff errors...
b) Real Arguments
-Catalan numbers may be generalized to real ( or even complex ) arguments via the formula:
Cx = 4x Gam(x+1/2) / [ sqrt(PI) Gam(x+2)
]
Data Registers: R00-R01: temp
Flags: /
Subroutine: "GAM" or "GAM+" ....
( cf "Gamma Function for the HP-41" )
| 01 LBL "CATX"
02 STO 00 03 2 04 + 05 XEQ "GAM" 06 STO 01 07 RCL 00 08 .5 09 + 10 XEQ "GAM" 11 4 12 RCL 00 13 Y^X 14 * 15 RCL 01 16 PI 17 SQRT 18 * 19 / 20 END |
( 38 bytes / SIZE 002 )
-Or if you have an M-Code routine "GAM"
| 01 LBL "CATX"
02 STO Y 03 .5 04 + 05 GAM 06 RCL Y 07 2 08 + 09 GAM 10 / 11 4 12 R^ 13 Y^X 14 PI 15 SQRT 16 / 17 * 18 END |
( 32 bytes / SIZE 000 )
| STACK | INPUTS | OUTPUTS |
| X | x | Cx |
Examples:
PI XEQ "CATX" gives CPI = 5.753085750
( in 4 seconds with GAM , in 7 seconds with XEQ "GAM" )
PI 1/X R/S
returns C1/PI = 0.850790775
2°) Generalized Catalan Numbers
a) Program#1
-Catalan numbers have many generalizations...
-The 2 following programs calculate the sequence 1 1
1 2 4 8 17 37 82 185 423
............... cf Sloane's A004148
-The coefficients are given by the recurrence relation:
a(0) = 1 , a(n+1) = a(n) + SUMk=1,2,...,n-1 a(k)
a(n-1-k)
Data Registers: R00 = a(0)
R01 = a(1) R02 = a(2) .........................
Rnn = a(n)
Flags: /
Subroutines: /
| 01 LBL "GCAT"
02 STO O 03 E3 04 / 05 3 06 + 07 STO M 08 SIGN |
09 STO 00
10 STO 01 11 STO 02 12 ENTER^ 13 LBL 01 14 CLX 15 STO N 16 LBL 02 |
17 RCL IND Y
18 RCL IND Y 19 * 20 ST+ N 21 SIGN 22 + 23 DSE Y 24 GTO 02 |
25 LASTX
26 + 27 RCL IND X 28 RCL N 29 + 30 STO IND M 31 ISG M 32 GTO 01 |
33 RCL O
34 SIGN 35 RCL IND L 36 CLA 37 END |
( 62 bytes / SIZE nnn+1 )
| STACK | INPUTS | OUTPUTS |
| X | n | a(n) |
| L | / | n |
Examples:
12 XEQ "GCAT" >>>> a(12) = 2283
---Execution time = 18s---
29 R/S
>>>> a(29) = 8622571758
---Execution time = 1mn53s---
41 R/S
>>>> a(41) = 5.442885873 E14
---Execution time = 3mn57s---
Notes:
-Execute SIZE at least 004 even if n = 0 , 1 , 2
-All the a(k) are stored in Rkk for k <= n
-Execution time becomes prohibitive for large arguments and another
approach is used hereunder:
b) Program#2
-If you only want one term, a(n) may also be computed by
a(n) = SUMk=m, m+1,.....,n
( Cn-kk Cn-k+1k ) / k
for n > 0 where
m = ceil [(n+1)/2] and Cnk = binomial
coefficients
Data Registers: R00 = k
R02 = 1 , 2 , 3 , .......
R01 = n R03 = ( Cn-kk
Cn-k+1k ) / k
Flags: /
Subroutines: /
-Lines 39-40-41 avoid roundoff errors when n < 30 ( for
instance if n = 23 )
-They may be replaced by the M-code routine RND0
( cf "A Few M-Code Routines for the HP-41" )
| 01 LBL "GCAT2"
02 STO 00 03 STO 01 04 SIGN 05 STO 02 06 STO 03 07 LBL 01 08 RCL 00 09 ST+ X |
10 RCL 01
11 - 12 ENTER^ 13 DSE X 14 ST* Y 15 ST* Y 16 DSE X 17 X<>Y 18 * |
19 X=0?
20 GTO 00 21 RCL 02 22 ISG 02 23 CLX 24 RCL 02 25 * 26 RCL 00 27 * |
28 DSE 00
29 RCL 00 30 * 31 / 32 RCL 03 33 * 34 STO 03 35 + 36 GTO 01 |
37 LBL 00
38 RDN 39 .1 40 + 41 INT 42 END |
( 62 bytes / SIZE 004 )
| STACK | INPUTS | OUTPUTS |
| X | n | a(n) |
Examples:
12 XEQ "GCAT2" >>>> a(12)
= 2283
---Execution time = 6s---
29
R/S
>>>> a(29) = 8622571758
---Execution time = 15s---
41
R/S
>>>> a(41) = 5.442885872 E14
---Execution time = 21s---
247 R/S
>>>> a(247) = 4.894614237 E99
---Execution time = 131s---
Note:
-This routine also works for n = 0
c) Another Definition
-Another type of generalized Catalan numbers is defined as:
An(a,b) = [ a/(a+nb) ] Cna+bn
where Cnm = binomial coefficients
Data Registers: /
Flags: /
Subroutine: "CNK" ( cf for instance "Statistics
& Probability for the HP-41" )
| 01 LBL "GCTL"
02 STO T 03 * 04 RCL Y 05 + 06 STO Z 07 R^ 08 XEQ "CNK" 09 R^ 10 / 11 * 12 END |
( 28 bytes / SIZE 000 )
| STACK | INPUTS | OUTPUTS |
| Z | a | / |
| Y | b | / |
| X | n | An(a,b) |
Example:
12 ENTER^
41 ENTER^
49 XEQ "GCTL" >>>> A49(12,41)
= 5.099194866 1096
Note:
An(1,2) = Cn
3°) Super-Catalan Numbers
a) Program#1
-The Super-Catalan numbers are given by the relations: S(0) = 1 , S(1) = 1 , S(2) = 3
S(n+1) = 3 S(n) + 2 SUMk=1,2,...,n-1 S(k) S(n-k)
-The first terms are 1 , 1 , 3 , 11 , 45 , 197 , 903 , 4279 ,
...................... cf Sloane's A001003
Data Registers: R00 = S(0)
R01 = S(1) R02 = S(2) .........................
Rnn = S(n)
Flags: /
Subroutines: /
| 01 LBL "SCAT"
02 STO O 03 E3 04 / 05 3 06 STO 02 07 + 08 STO M 09 SIGN |
10 STO 00
11 STO 01 12 LBL 01 13 RCL M 14 INT 15 2 16 - 17 STO N 18 SIGN |
19 0
20 LBL 02 21 RCL IND Y 22 RCL IND N 23 * 24 + 25 ISG Y 26 CLX 27 DSE N |
28 GTO 02
29 ST+ X 30 RCL IND Y 31 3 32 * 33 + 34 STO IND M 35 ISG M 36 GTO 01 |
37 RCL O
38 SIGN 39 RCL IND L 40 CLA 41 END |
( 67 bytes / SIZE nnn+1 )
| STACK | INPUTS | OUTPUTS |
| X | n | S(n) |
| L | / | n |
Example:
15 XEQ "SCAT" >>>> S(15) = 1968801519 ---Execution time = 36s---
Notes:
-Execute SIZE at least 004 even if n = 0 , 1 , 2
-All the S(k) are stored in Rkk for k <= n
b) Program#2
-They are also defined by the recurrence relation:
(n+1) S(n) = (6n-3) S(n-1) - (n-2) S(n-2) if n > 1 and S(0) = S(1) = 1
-In fact, this relation holds for n = 0 and n = 1 if we define
S(-1) = S(0) = -1
Data Registers: R00 = counter
R01 = S(n-1) R02 = n
Flags: /
Subroutines: /
| 01 LBL "SCAT2"
02 E3 03 / 04 STO 00 05 SIGN 06 CHS 07 STO 01 |
08 LBL 01
09 2 10 RCL 00 11 INT 12 STO 02 13 - 14 RCL 01 |
15 *
16 RCL 02 17 6 18 * 19 3 20 - 21 R^ |
22 STO 01
23 * 24 + 25 RCL 02 26 1 27 + 28 / |
29 ISG 00
30 GTO 01 31 END |
( 44 bytes / SIZE 003 )
| STACK | INPUTS | OUTPUTS |
| Y | / | S(n-1) |
| X | n | S(n) |
Example:
132 XEQ "SCAT2" >>>> S(132) = 2.989194489
1097
---Execution time = 116s---
RDN S(131) = 5.187141727 1096 = R01
c) Program#3
-Legendre polynomials Pn also allow to compute the Super-Catalan numbers S(n) if n > 0
S(n) = [ 3 Pn(3) - Pn-1(3)
] / ( 4n+4 )
Data Registers: R00 = n
Flags: /
Subroutine: "LEG" ( cf "Orthogonal
Polynomials for the HP-41" )
-Replace R00 by R03 if you have replaced M N O by R00 R01 R02 in the
"LEG" listing.
| 01 LBL "SCAT3"
02 1 03 X>Y? 04 RTN 05 X<>Y 06 STO 00 07 3 08 XEQ "LEG" 09 .75 10 * 11 X<>Y 12 4 13 / 14 - 15 RCL 00 16 1 17 + 18 / 19 END |
( 35 bytes / SIZE 001 )
| STACK | INPUTS | OUTPUTS |
| X | n | S(n) |
Examples:
132 XEQ "SCAT3" >>>> S(132) = 2.989194493
1097
---Execution time = 75s---
15
R/S >>>>
S(15) = 1968801519
---Execution time = 9s---
4°) Super-Catalan Numbers of order m
-Another type of "Super-Catalan numbers" is defined as
C(n,m) = Cn2n Cm2m / [ 2 Cnm+n
] where Ckn = n! /
[ k! (n-k)! ]
-All these terms are integers except C(0,0) = 1/2
Data Register: R00 = n+m , n+m-1 , ...............
, 1 , 0
Flags: /
Subroutines: /
-Lines 09-10-30-31 are only useful if n = m = 0. Otherwise,
they can be deleted.
| 01 LBL "SCTL"
02 ENTER^ 03 ENTER^ 04 + 05 X<>Y 06 R^ 07 ST+ T |
08 +
09 X=0? 10 SIGN 11 STO 00 12 SIGN 13 ST- Y 14 ST- Z |
15 2
16 / 17 LBL 01 18 X<>Y 19 X<0? 20 X<> Z 21 ST* Y |
22 X<>Y
23 2 24 ST- Z 25 * 26 RCL 00 27 / 28 DSE 00 |
29 GTO 01
30 X<0? 31 .5 32 END |
( 50 bytes / SIZE 000 )
| STACK | INPUTS | OUTPUTS |
| Y | n | / |
| X | m | C(n,m) |
Examples:
103 ENTER^
208 XEQ "SCTL" >>>> C(103,208) = 6.694759032
1099 ---Execution
time = 132s---
168 ENTER^ R/S >>>> C(168,168) = 3.044358792 1099 ---Execution time = 143s---
Notes:
-Though C(n,m) = C(m,n) , small differences in the last places are possible
- due to roundoff errors.
-For instance 208 ENTER^ 103 R/S gives
6.694759074 E99 whereas an HP-48 returns 6.69475904935
E99
-If you replace R00 by synthetic register M , "SCTL" becomes a SIZE
000 program ( slightly faster ).
-The first few terms are:
n\m 0 1 2 3 4 5
0 .5
1 3 10 35 126
1 1
1 2 5 14 132
2 3
2 3 6 14 36
3 10
5 6 10 20 45
4 35 14
14 20 35 70
5 126 42 36
45 79 126
- C(1,n) = C(n,1) are "the" Catalan numbers Cn
References:
[1] http://functions.wolfram.com/
[2] http://www.research.att.com/~njas/sequences/Seis.html
[3] David Callan - "Journal of Integer Sequences" Vol.
8 ( 2005 ) Article 05.1.8