(42S) Subfactorial
09-06-2021, 04:43 PM
Post: #1
 Eddie W. Shore Senior Member Posts: 1,493 Joined: Dec 2013
(42S) Subfactorial
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.

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