(42S) Subfactorial
09-12-2021, 12:46 PM
Post: #12
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
RE: (42S) Subfactorial
(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)
 « Next Oldest | Next Newest »

 Messages In This Thread (42S) Subfactorial - Eddie W. Shore - 09-06-2021, 04:43 PM RE: (42S) Subfactorial - John Keith - 09-06-2021, 06:50 PM RE: (42S) Subfactorial - Albert Chan - 09-07-2021, 02:21 PM RE: (42S) Subfactorial - Werner - 09-09-2021, 07:24 AM RE: (42S) Subfactorial - Albert Chan - 09-09-2021, 03:33 PM RE: (42S) Subfactorial - Albert Chan - 09-08-2021, 10:26 PM RE: (42S) Subfactorial on HP-15C - C.Ret - 09-11-2021, 04:15 PM RE: (42S) Subfactorial - Werner - 09-09-2021, 07:45 AM RE: (42S) Subfactorial - Werner - 09-09-2021, 12:31 PM RE: (42S) Subfactorial - ijabbott - 09-11-2021, 08:24 AM RE: (42S) Subfactorial - Gil - 09-12-2021, 12:05 AM RE: (42S) Subfactorial - Albert Chan - 09-12-2021 12:46 PM

User(s) browsing this thread: 1 Guest(s)