(42S) Subfactorial

[Eddie W. Shore]

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

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