Swiss Micros DM42: Subfactorial
Happy Labor Day!
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.
Swiss Micros DM42 Program: Subfactorial Version 1
This is a traditional route. Registers used:
R01: k, counter
R02: sum register
R03: n!, later !n
Program labels can start with symbols on the 42S.
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
Swiss Micros DM42 Program: Subfactorial Version 2
I only put 2 in the label to distinguish the two programs.
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
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!9 = 133,496
!14 ≈ 3.2071E10
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
Numworks 16.3 Update
Numworks recently updated its firmware to Version 16.3. Find details of the changes and additions here:
https://my.numworks.com/firmwares
All original content copyright, © 2011-2021. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.