Sunday, July 24, 2022

Deriving Derangement Theorem

5 - Deriving Derangement Theorem Go to Index of Math Lessons

Deriving Derangement Theorem

The growth of both the functions n! (factorial) and !n (derangement) is exponential, look at the table of values below:

n Permutation Derangement
2 2 1
3 6 2
4 24 9
5 120 44
6 720 265
7 5040 1854

We will work with the log (base Math.E) of these functions. Look at the table of values below:

n log(Permutation) log(Derangement)
2 0.693 0
3 1.791 0.693
4 3.178 2.197
5 4.787 3.784
6 6.5792 5.5797
7 8.5251 7.5251

We see the following relationship between these values:
log(!n) = log(n!) - 1
=> log(!n) = log(n!) - log(e)
=> log(!n) = log(n! / e)
=> !n = n! / e
And true relationship between !n and n! is: !n = round(n! / e)

Test this out by adding data to the plot showing n! and !n below:


Tags: Mathematical Foundations for Data Science,

No comments:

Post a Comment