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