Catalan

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