(42S) Subfactorial

[Albert Chan]

(09-12-2021 12:05 AM)Gil Wrote:  Dividing 30! by 2.718281828... (100 digits) gives
the following digits: 97581073836835777732377428235480.9687...

The above rounded number is then correctly the one given in the previous post ending by 481.

Thanks, Gil

If we consider removed fractional part, (1-0.9687) = 0.0313 ≈ 0.970/31

Let P(n) = !n/n!, abs_error(P(30)) < 1/31!

Consider only n-th element, probability of derangemnt = 1-1/n
(i.e. n-th element cannot be at n-th place)

To count derangements, we have to remove over-counted cases.
Example: 12345 has all elements in the wrong spots.

Recursively apply Inclusion Exclusion Principle to remove over-counts:

P(n) = 1 - 1/1*(1 - 1/2*(1 - 1/3*( ... (1 - 1/(n-1)*(1-1/n)))))
       = 1 - 1 + 1/2! - 1/3! + 1/4! - ... + (-1)^n/n!

1/e  = 1 - 1 + 1/2! - 1/3! + 1/4! - ... + (-1)^n/n! + (-1)^(n+1)/(n+1)! + ...

With alternate signs, abs_error( P(n)-1/e ) < 1/(n+1)!

→ abs_error( !n - n!/e ) < 1/(n+1)

For n≥1, 1/(n+1) ≤ 1/2 : !n = round(n!/e)