(42S) Subfactorial
|
09-12-2021, 12:46 PM
Post: #12
|
|||
|
|||
RE: (42S) Subfactorial
(09-12-2021 12:05 AM)Gil Wrote: Dividing 30! by 2.718281828... (100 digits) gives 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)