hp41programs

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  .
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