Calculating the Subfactorial

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.

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.