(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.

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
 « Next Oldest | Next Newest »

 Messages In This Thread (42S) Subfactorial - Eddie W. Shore - 09-06-2021 04:43 PM RE: (42S) Subfactorial - John Keith - 09-06-2021, 06:50 PM RE: (42S) Subfactorial - Albert Chan - 09-07-2021, 02:21 PM RE: (42S) Subfactorial - Werner - 09-09-2021, 07:24 AM RE: (42S) Subfactorial - Albert Chan - 09-09-2021, 03:33 PM RE: (42S) Subfactorial - Albert Chan - 09-08-2021, 10:26 PM RE: (42S) Subfactorial on HP-15C - C.Ret - 09-11-2021, 04:15 PM RE: (42S) Subfactorial - Werner - 09-09-2021, 07:45 AM RE: (42S) Subfactorial - Werner - 09-09-2021, 12:31 PM RE: (42S) Subfactorial - ijabbott - 09-11-2021, 08:24 AM RE: (42S) Subfactorial - Gil - 09-12-2021, 12:05 AM RE: (42S) Subfactorial - Albert Chan - 09-12-2021, 12:46 PM

User(s) browsing this thread: 1 Guest(s)