Calculating the Subfactorial

Posted on by

Difficulty: ★ ★ ★ ★

Calculating a factorial is a common programming exercise, often coupled with introducing the concept of recursion. Mathematically, the factorial has a twin: the subfactorial. Its calculation can be a fun programming challenge, which is the subject of this month’s Exercise.

As a review, a factorial is a value written as n!. The value represents integer n multiplied sequentially. For example, 5! is 1×2×3×4×5, which equals 120. This value is the number of permutations possible with five items.

Figure 1 illustrates 3! or three factorial. It shows the number of ways to arrange three objects, which is what 3! represents.

Three factorial

Figure 1. The value 3! shows how many ways to arrange three objects. 3! = 6 different arrangements.

The subfactorial works along similar lines. It’s written with the exclamation point before the value: subfactorial three is !3. The subfactorial limits the arrangements so that no objects can be in the same position as in the original. Value !3 calls out all non-unique arrangements for three objects. An example is shown in Figure 2.

Figure 2. Three subfactorial (!3) shows that only two arrangements are possible when compared with the original. !3 = 2.

The best explanation of the subfactorial process, also called derangement, is found in this video from Andy Math. Do take time to watch it, as it describes a formula you can use to calculate subfactorials. The formula is illustrated in Figure 3.

Figure 3. The equation for calculating a subfactorial.

Your task for this month’s Exercise is to write code that outputs values for subfactorials !0 through !13. You can use the equation from Figure 3 as your inspiration, which is what I did. You can also check out the Derangement Wikipedia page, which offers more formulas and mathematical mumbojumbo.

Here is output from my solution, the list of subfactorial values for !0 through !13:

!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

As with factorials, these subfactorials are known values, though you can’t just write a solution that outputs the results shown above. No, you must code a solution in C.

Try this Exercise on your own before you check out my solution.

3 thoughts on “Calculating the Subfactorial”

  1. ” . . . you can’t just write a solution that outputs the results shown above”. Why not? That’s the sort of thing people on Instagram do! Possibly not the world’s greatest source of programming expertise though.

    Is Andy Math his real name? 🙂

    I don’t understand the meaning of !0. The result implies that if you have zero squares, circles and triangles (for example) there is 1 unique way of rearranging them which obviously doesn’t make sense. I’d have assumed !0 was undefined.

    According to Wikipedia the easy way is n!/e (e being Euler’s number) but it gets increasingly inaccurate as n gets larger. Maybe you need e to gazillions of decimal places.

    Anyway, this is my solution. I pre-calculated the factorials in an array. I might have gone a bit over the top with doubles but I didn’t want to risk losing any precision. They might not be entirely necessary but I couldn’t be bothered to try downsizing.

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>

    int main()
    {
        long factorials[14];
        double subfactorial;
        double interim;
        // const float e = 2.71828; // inaccurate from !10
        const float e = 2.7182818284590452353602874713527; // inaccurate from !11

        factorials[0] = 1;
        factorials[1] = 1;

        // pre-calculate factorials
        for(int i = 2; i <=13; i++)
        {
            factorials[i] = factorials[i-1] * i;
        }

        // the n!/e method
        for(int n = 1; n <= 13; n++)
        {
            subfactorial = round(factorials[n]/e);

            printf(“%d\t%.0lf\n”, n, subfactorial);
        }

        puts(“\n———————\n”);

        // the complicated method
        for(double n = 0; n <= 13; n++)
        {
            interim = 0;

            for(double k = 0; k <= n; k++)
            {
                interim += ( pow(-1.0, k) / factorials[(int)k] );
            }

            subfactorial = factorials[(int)n] * interim;

            printf(“%d\t%.0lf\n”, (int)n, subfactorial);
        }

        return EXIT_SUCCESS;
    }

  2. The explanation behind !0 is that when you have zero object there is only one way to arrange them: Not at all. I’ve seen other proofs as well, though this is the one I remember.

    Thanks for the solution!

  3. I messed that up. I declared e as a float but should have used double. I changed it and got correct results up to !13. (Possibly higher but I didn’t check.)

    BUT the n!/e method gives !0 as 0. I still don’t understand because the example with 3 shapes in fig. 2 shows that the subfactorial is the number of ADDITIONAL ways of arranging items therefore both !0 and !1 should be 0. (Assuming !0 is valid anyway which I’m still dubious about.)

    Actually I’m also not sure why 0! = 1. Probably just due to mathematicians being a bit mad.

Leave a Reply