Calculating the Subfactorial – Solution

Do you feel adequately deranged working this month’s Exercise? I’m more of a math fanboy than an expert, yet I enjoyed the process of coding a subfactorial based in the equation presented.

My solution does require a recursive function to determine a factorial; factorials are needed when calculating a subfactorial. But my derange() function need not be recursive. It’s sequential, which is obvious when looking at the formula shown in Figure 1.

Figure 1. The equation for calculating a subfactorial.

Recursive functions work well for continued fractions, but the equation in Figure 1 is finite. A loop is sufficient to plow through the values and arrive at the proper subfactorial value. Here is my solution:


#include <stdio.h>

long factorial(long f)
    if( f<=1 )

long derange(long d)
    long r,t;

    r = 0;
    t = factorial(d);
        r += (d%2 ? -1 : 1)*t/factorial(d);


int main()
    long a;

    for(a=0; a<14; a++)
        printf("!%ld = %ld\n",a,derange(a));

    return 0;

My code uses long integers throughout. Yes, I originally used the int data type, but it’s too narrow to obtain the larger values.

The main() function loops through values zero through 13, calling the derange() function in a printf() statement.

The derange() function obtains the factorial of the value passed, d. Then a while loop works through the equation flipping between positive and negative values multiplied by the factorial of the original value of d and divided by the current factorial of d. This expression is how I interpret the equation from Figure 1. The result is returned in variable r.

The factorial() function is recursive, mirroring a post I wrote a while back. I did update the code so that the if test evaluates f<=1, which accounts for !0.

Here is a sample run:

!0 = 1
!1 = 0
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!6 = 265
!7 = 1854
!8 = 14833
!9 = 133496
!10 = 1334961
!11 = 14684570
!12 = 176214841
!13 = 2290792932

These are the values you must see to gauge your solution's success.

My solution is only one approach, and the equation I use is only one way to reveal subfactorials. I hope your solution is successful, but that you also enjoyed coding it as much as I did mine.

Leave a Reply