- General formula: !n=(n-1)[!(n-1)+!(n-2)]
- !0=1
- !1=0
We're glad that you asked. The n th 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