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).

So, if we have the digits {1, 2, 3, 4} (n=4), we want to know how many ways can we order those numbers such that none appear in their initial position (so, "1" will not be first; "2" will not be second, "3" will not be third, and "4" will not be fourth).

The following combinations of {1, 2, 3, 4} are the only combinations in which no digit is in its natural place:
{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 9 possible combinations that meet this criterion. So !4=9.

Remember that there are 4! (=24) possible combinations of {1, 2, 3. 4}, so we note that
4!-!4=24-9=15
 of them have a value that is in its natural place.

The following is a list of combinations that do not meet the criterion (that is, at least one of the four digits is in its "natural" place) 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)

[Note that there is no case in which 3 fail, since if 3 of these values are in the right place, the remaining value must be in the right place, too.]

Mathematically we can use a recursive approach:
!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

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

Popular posts from this blog

Sum-thing else

In addition to the recursion formulas shown, a subfactorial  can be developed using a summation. As an example, we'll develop the result for !4 , which we have addressed in an earlier post. ...which is the same answer we developed using the recursion  approach.