# 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:

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