09-06-2021, 04:43 PM
This is a request by Marko Draisma and gratitude to Mr. Draisma.
Calculating the Subfactorial
A common, and perhaps the most straight forward, formula to calculate the subfactorial is:
!n = n! × Σ((-1)^k ÷ k!, k=0 to n)
Yes, the subfactorial is written with the exclamation point first. The subfactorial finds all the possible arrangements of a set of objects where none of the objects end up in their original position.
For example, when arranging the set {1, 2, 3, 4} the subfactorial counts sets such as {2, 1, 4, 3} and {3, 4, 1, 2} but not {1, 4, 3, 2}. For the positive integers: !n < n!.
I am going to present two programs. The first will use the formula stated above.
The second uses this formula, which will not require recursion or loops:
!n = floor[ (e + 1/e) × n! ] - floor[ e × n! ]
Note: Since the N! function on the DM42 accepts only positive integers, we can use the IP (integer part) to simulate the floor function.
integer(x) = { floor(x) if x ≥ 0, ceiling(x) if x < 0
The following programs can be used on Free42, HP 42S, or Swiss Micros DM42.
Version 1: The Traditional Route
Registers used:
R01: k, counter
R02: sum register
R03: n!, later !n
Version 2: Closed Formula
I only put 2 in the label to distinguish the two programs.
Examples
!4 = 9
!5 = 44
!9 = 133,496
Sources:
"Calculus How To: Subfactorial" College Help Central, LLC .https://www.calculushowto.com/subfactorial/ Retrieved September 5, 2021.
Weisstein, Eric W. "Subfactorial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Subfactorial.html Retrieved September 5, 2021
Blog Link: http://edspi31415.blogspot.com/2021/09/s...orial.html
Calculating the Subfactorial
A common, and perhaps the most straight forward, formula to calculate the subfactorial is:
!n = n! × Σ((-1)^k ÷ k!, k=0 to n)
Yes, the subfactorial is written with the exclamation point first. The subfactorial finds all the possible arrangements of a set of objects where none of the objects end up in their original position.
For example, when arranging the set {1, 2, 3, 4} the subfactorial counts sets such as {2, 1, 4, 3} and {3, 4, 1, 2} but not {1, 4, 3, 2}. For the positive integers: !n < n!.
I am going to present two programs. The first will use the formula stated above.
The second uses this formula, which will not require recursion or loops:
!n = floor[ (e + 1/e) × n! ] - floor[ e × n! ]
Note: Since the N! function on the DM42 accepts only positive integers, we can use the IP (integer part) to simulate the floor function.
integer(x) = { floor(x) if x ≥ 0, ceiling(x) if x < 0
The following programs can be used on Free42, HP 42S, or Swiss Micros DM42.
Version 1: The Traditional Route
Registers used:
R01: k, counter
R02: sum register
R03: n!, later !n
Code:
01 LBL "!N"
02 STO 01
03 N!
04 STO 03
05 0
06 STO 02
07 RCL 01
08 1E3
09 ÷
10 STO 01
11 LBL 00
12 RCL 01
13 IP
14 ENTER
15 ENTER
16 -1
17 X<>Y
18 Y↑X
19 X<>Y
20 N!
21 ÷
22 STO+ 02
23 ISG 01
24 GTO 00
25 RCL 02
26 RCL× 03
27 STO 03
28 RTN
Version 2: Closed Formula
I only put 2 in the label to distinguish the two programs.
Code:
01 LBL "!N 2"
02 N!
03 ENTER
04 ENTER
05 1
06 E↑X
07 ENTER
08 1/X
09 +
10 ×
11 IP
12 X<>Y
13 1
14 E↑X
15 ×
16 IP
17 -
18 RTN
Examples
!4 = 9
!5 = 44
!9 = 133,496
Sources:
"Calculus How To: Subfactorial" College Help Central, LLC .https://www.calculushowto.com/subfactorial/ Retrieved September 5, 2021.
Weisstein, Eric W. "Subfactorial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Subfactorial.html Retrieved September 5, 2021
Blog Link: http://edspi31415.blogspot.com/2021/09/s...orial.html