Skip to main content

Seriously...I don't have time to click the links on this page. What the f**k is a subfactorial?

We're glad that you asked.

The nth subfactorial is the number of permutations of n objects in which no object appears in its natural place (from Wolfram)

Example

If we have the digits {1, 2, 3, 4} (n=4), the formula shown is
!n=(n-1)[!(n-2)+!(n-1)] with !0=1 and !1=0
Then
!4=(3)[!2+!3] so we need !2 and !3
!2=(1)[!0+!1]=1[1+0]=1
!3=(2)[!1+!2]=2[0+1]=2
And, finally
!4=(3)[!2+!3]=3[1+2]=9

Let's check that out.
The following combinations are the only ones in which any digit is not in its natural place (1 is not in the first location and/or 2 is not in the second and/or 3 is not in the third and/or 4 in the fourth):
2, 1, 4, 3
2, 3, 4, 1
2, 4, 1, 3
3, 1, 4, 2
3, 4, 1, 2
3, 4, 2, 1
4, 1, 2, 3
4, 3, 1, 2
4, 3, 2, 1
There are (as we calculated), there are 9. No surprise!

Notice that there are 4! (=24) possible combinations, but n!-!n=24-9=15 of them have a value that is in its natural place. The following list are those combinations that do not meet the requirement along with an explanation of why these combinations to not meet the requirement:

1, 2, 3, 4 (all digits fail)
1, 2, 4, 3 (1 and 2 fail)
1, 3, 2, 4 (1 and 4 fail)
1, 3, 4, 2 (1 fails)
1, 4, 2, 3 (1 fails)
1, 4, 3, 2 (1 and 3 fail)
2, 1, 3, 4 (3 and 4 fail)
2, 3, 1, 4 (4 fails)
2, 4, 3, 1 (3 fails)
3, 1, 2, 4 (4 fails)
3, 2, 1, 4 (2 and 4 fail)
3, 2, 4, 1 (2 fails)
4, 1, 3, 2 (3 fails)
4, 2, 1, 3 (2 fails)
4, 2, 3, 1 (2 and 3 fail)

Popular posts from this blog