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,

Ex 4 - Problem on Derangement Theorem

Derangement Theorem Go to Index of Math Lessons

Ques: There are four balls of different colors and four boxes of the same colors as of the balls. Find the number of ways in which the balls, one in each of the box, could be placed such that the ball does not go to the box of its own color.

Ans: This problem comes directly from the 'derangement theorem'.

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

If A, B, C, D are four balls and a, b, c, d are four boxes then derangements are:

Let the number of balls be:  
Then, the balls are:  
And, the boxes are:  
All derangements of the balls are:   {{generateDerangements()}}
The number of derangements of 'n' balls is equal to: round(n!/e) = {{generateDerangementsCount()}}
Tags: Mathematical Foundations for Data Science,