The Museum of HP Calculators

# Stirling Numbers for the HP-41

This program is by Jean-Marc Baillard and is used here by permission.

This program is supplied without representation or warranty of any kind. Jean-Marc Baillard and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

Overview

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

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 ----------------------------------  ( sn0 = 0 )  ;   snm =  sn-1m-1  +  m sn-1m            --------------

•  (-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.
--------   set,   ------------------------------------------- second kind.
Subroutine:  none

-Synthetic registers M , N , O may be replaced by any unused data registers.

01  LBL "SNM"
02  STO N
03   E3
04  ST/ Z
05  /
06  CLRGX                   if you don't have an HP-41CX,  replace line 06 by   SIGN  CLX  LBL 00  STO IND L  ISG L  GTO 00
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)

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

Example:   Calculate  S127   and    s127

a)  CF 02
12  ENTER^
7  XEQ "SNM"   yields ( in 27 seconds )   S127 =  -2637558      ( and R01 = -39916800 = S121 ; R02 = 120543840 = S122
.........................................      R07 = -2637558 = S127  )

b)  SF 02
12  ENTER^
7     R/S          produces ( in 27 seconds )   s127 = 627396       ( and R01 = 1 =  s121 ; R02 = 2047 =  s122 ; ........ ;  R07 = 627396 = s127 )

-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.
--------   set,   ------------------------------------------------ second kind.
Subroutine:  none

-Synthetic registers M , N , O , P  may be replaced by any unused data registers.

01  LBL "SKNM"
02  STO N
03   E3
04  ST/ Z
05  /
06  CLRGX                   if you don't have an HP-41CX,  replace line 06 by   SIGN  CLX  LBL 00  STO IND L  ISG L  GTO 00
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                 ( synthetic )
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)

where  S(k;n,m) is the k-Stirling number of the first kind if flag F02 is clear
or ------------------------- second --------  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