Subfactorial

The subfactorial, also known as the derangement number or the coincidence number, is a combinatorial function that counts the number of permutations of a set of objects such that no object appears in its original position. It is often denoted by !n or D_n, where n is a non-negative integer.

For a set of size n, a derangement is a permutation p where for all elements i in the set, p(i) != i. For example, if we have the set {1, 2, 3}, the permutations are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). The derangements are (2, 3, 1) and (3, 1, 2), because in these permutations, no number is in its original position. Therefore, the subfactorial of 3, !3, is 2.

The subfactorial can be calculated using a recursive formula: !n = (n-1) * (!(n-1) + !(n-2)) for n >= 2, with base cases !0 = 1 and !1 = 0. Alternatively, it can be computed using the formula !n = n! * sum((-1)^k / k!) for k from 0 to n. This latter formula is derived from the principle of inclusion-exclusion.

The subfactorial function grows rapidly with n. The first few values are !0 = 1, !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44, and !6 = 265. The subfactorial is closely related to the number e, the base of the natural logarithm. As n approaches infinity, the ratio of !n to n! approaches 1/e.