Skip to main content

Seriously...I don't have time to click the links on this page. What's "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 result 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
!3=(2)[!1+!2]=2[0+1]=2 so we still need !2
!2=(1)[!0+!1]=1[1+0]=1

Finally,
!4=(3)[!2+!3]=3[1+2]=9

Let's check that out.
The following combinations are the only ones in which no digit is in its natural place (1 is not in the first location, 2 is not in the second, 3 is not in the third, 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
As we calculated, there are 9 possible combinations. No surprise!

But there are 4! (=24) possible combinations of 1; 2; 3; 4 and n!-!n=24-9=15 of them have a value that is in its natural place.

The following list is those combinations that do not meet the requirement along with an explanation of why these combinations do 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)

On a scale from !0 to !4, how happy are you that you asked?

Popular posts from this blog