hp41programs

Stirling Stirling Numbers for the HP-41
 

Overview
 

 1°) Stirling Numbers of the first & second kind
 2°) A Generalization: k-Stirling Numbers
 
 

1°) Stirling Numbers of the first and second kind
 

-Stirling numbers of the first kind Snm are defined by the recurrence relation: ( Sn0 = 0 ) ;  Snm = Sn-1m-1 - ( n-1 ) Sn-1m      ( 1 <= m <= n )
-Stirling numbers of the second kind snm are defined by the recurrence relation:  ( sn0 = 0 )  ;   snm =  sn-1m-1  +  m sn-1m      ( 1 <= m <= n )

  •  (-1)n-m Snm is the number of permutations of n symbols which have exactly m cycles.
  •             snm  is the number of ways of partitioning a set of n elements into m non-empty subsets.
 

Data Registers:       When the program stops:   R00 = 0 , R01 = Sn1 , R02 = Sn2 , ...... , Rmm = Snm       ( or snj  if F02 is set )

Flags:   if F02 is clear, "SNM" calculates the Stirling numbers of the first kind.
             if F02 is  set, "SNM" calculates the Stirling numbers of the second kind.

Subroutines:  /

-Synthetic registers M , N , O may be replaced by any unused data registers.
-If you don't have an HP-41CX,  replace line 06 by   SIGN  CLX  LBL 00  STO IND L  ISG L  GTO 00
 
 

01  LBL "SNM"
02  STO N
03   E3
04  ST/ Z
05  /
06  CLRGX 
07  SIGN
08  STO 01
09  +		 10  STO M       
11  LBL 01
12  RCL M
13  ISG M
14  X=0?
15  GTO 03
16  INT
17  CHS
18  STO O		 19  RCL M       
20  INT
21  RCL N
22  X>Y?
23  X<>Y
24   E3
25  /
26  RCL 00
27  ISG Y		 28  LBL 02
29  FC? 02
30  RCL O
31  FS? 02
32  RCL Y
33  INT
34  RCL IND Z
35  *
36  +		 37  X<> IND Y
38  ISG Y
39  GTO 02
40  GTO 01
41  LBL 03
42  RCL IND N
43  CLA
44  END

 
   ( 75 bytes / SIZE m+1 ( but at least 002 ))
 
 

      STACK        INPUTS      OUTPUTS
           Y             n             /
           X         m <= n         s(n;m) 

     s(n;m) is the Stirling number of the first kind if flag F02 is clear
     s(n;m) is the Stirling number of the second kind if flag F02 is set.

Example:   Calculate  S127   and    s127

        CF 02
        12  ENTER^
          7  XEQ "SNM"   yields ( in 27 seconds )   S127 =  -2637558

     ( and R01 = -39916800 = S121 ; R02 = 120543840 = S122    .........................................      R07 = -2637558 = S127  )

        SF 02
        12  ENTER^
         7     R/S          produces ( in 27 seconds )   s127 = 627396

     ( and R01 = 1 =  s121 ; R02 = 2047 =  s122 ; ........ ;  R07 = 627396 = s127 )

Note:

-Some authors define the Stirling numbers of the first kind as  Snm = Sn-1m-1 + ( n-1 ) Sn-1m  instead of   Snm = Sn-1m-1 - ( n-1 ) Sn-1m
-If you prefer this formula, simply delete line 17  ( the difference is only a change of sign: all results are positive )
 

2°) A Generalization: k-Stirling Numbers
 

  •    k-Stirling numbers of the first kind S1(k;n,m) are defined by the recurrence relation:

                 S1(k;0,0) = 0     ;      S1(k;n,m)  =  [ (1-k).m + 1 - n ] S1(k;n-1,m) + S1(k;n-1,m-1)    ( 1 <= m <= n )

  •    k-Stirling numbers of the second kind S2(k;n,m) are defined by:

                 S2(k;0,0) = 0     ;      S2(k;n,m)  =  [ (k-1).(n-1) + m ] S2(k;n-1,m) + S2(k;n-1,m-1)    ( 1 <= m <= n )
 

Data Registers:      When the program stops:   R00 = 0 , R01 = S(k;n,1) , R02 = S(k;n,2) , ...... , Rmm = S(k;n,m)

Flags:   if F02 is clear, "SKNM" calculates the k-Stirling numbers of the first kind.
             if F02 is  set, "SKNM" calculates the k-Stirling numbers of the second kind.

Subroutines:  /

-Synthetic registers M , N , O , P  may be replaced by any unused data registers.
-If you don't have an HP-41CX,  replace line 06 by   SIGN  CLX  LBL 00  STO IND L  ISG L  GTO 00
 
 

01  LBL "SKNM"
02  STO N
03   E3
04  ST/ Z
05  /
06  CLRGX   
07  SIGN
08  STO 01
09  ST- Z
10  +
11  STO M
12  X<>Y		 13  STO O          
14  LBL 01
15  RCL M
16  ISG M
17  X=0?
18  GTO 04
19  INT
20  RCL M
21  INT
22  RCL N
23  X>Y?
24  X<>Y		 25   E3
26  /
27  R^
28  STO P          
29  CLX
30  ISG Y
31  LBL 02
32  RCL O
33  FS? 02
34  GTO 02
35  RCL Z
36  INT		 37  *
38  RCL P          
39  +
40  CHS
41  GTO 03
42  LBL 02
43  RCL P
44  *
45  RCL Z
46  INT
47  +
48  LBL 03		 49  RCL IND Z
50  *
51  +
52  X<> IND Y
53  ISG Y
54  GTO 02
55  GTO 01
56  LBL 04
57  RCL IND N
58  CLA
59  END

 
   ( 97 bytes / SIZE max( 2 , m+1) )
 
 

      STACK        INPUTS      OUTPUTS
           Z             k             /
           Y             n             /
           X         m <= n         S(k;n,m) 

     S(k;n,m) is the k-Stirling number of the first kind if flag F02 is clear
     S(k;n,m) is the k-Stirling number of the second kind if flag F02 is set.

    ( k may be positive, zero or negative )

Example:

  CF 02   3  ENTER^  10  ENTER^  7   XEQ "SKNM"   >>>>   S1(3;10,7) = -188370   ( in 28 seconds )
  SF 02    3  ENTER^  10  ENTER^  7           R/S            >>>>   S2(3;10,7) =  220500   ( in 27 seconds )

-In both cases,      R01 = Si(3;10,1)   R02 = Si(3;10,2)  ..................  R07 = Si(3;10,7)    ( i = 1 or 2 )

Note:    S1(1;n,m) = Snm     ;      S2(1;n,m) = snm
 

References:

[1]  Abramowitz & Stegun - "Handbook of Mathematical Functions" -  Dover Publications    ISBN 0-486-61272-4
[2]  Wolfdieter Lang - "On Generalizations of the Stirling Number Triangles" - Journal of Integer Sequences
[3]  N.J.A. Sloane's On-Line Encyclopedia of Integer Sequences:   www.research.att.com/~njas/sequences