Mathematics
Bernoulli-Euler problem of misaddressed letters
How many ways to distribute n distinct letters into n corresponding envelops so that no letter gets to its corresponding envelops?
Removing the words” letter” and” envelops” from this problem, we really want to know that how many permutations of {1, 2, … , n } there are such that k is not at kth place for any k (1 ≤ k ≤ n)? These permutations are called the derangements, and we denote the number of derangements by Dn.
Let S be the set of permutations of {1, 2, … , n } and Ai the set of permutations {a1, a2, … , an, } of {1, 2, … , n} satisfying ai = i (i = 1, 2, … , n). Obviously, we have
By the sieve formula, we get,
Permutation and its fixed point Let X = {1, 2, … , n } , φ be a bijective mapping between X and X. Then φ is called a permutation on X and we usually write a permutation as follows:
For i EX, if i ∈ X, if φ(i) = i , then i is called a fixed point of permutation φ on X.
Thank you for taking your time to read my article. Please don’t forget to hit the clap button if you liked it. Your feedbacks and suggestions are highly welcomed and appreciated.
