Derangements - Art of Problem Solving

Combinatorics is the branch of mathematics which entails the study of combinations and permutations of sets of elements and their relations. A permutation is simply the rear- rangement of the elements of a set where the order has significance, whereas a combination is a selection of elements with disregard to order.
191KB Sizes 94 Downloads 459 Views
Derangements Poojit Hegde June 2015 This report will discuss the theory of derangements, a topic in discrete mathematics. Some examples will also be discussed along with some extensions.

1

Background

Combinatorics is the branch of mathematics which entails the study of combinations and permutations of sets of elements and their relations. A permutation is simply the rearrangement of the elements of a set where the order has significance, whereas a combination is a selection of elements with disregard to order. For example, 1,2 and 2,1 are the same combination, yet they are different permutations. The study of derangements is an application of a permutation. They were first studied by Pierre Remond de Montmort, a famous French mathematician, who also studied probability and finite differences. He came up with the problem of derangements in 1708 and solved it in 1713. A different method of solution was later found Nicholas Bernoulli, using the principle of inclusion and exclusion. Many years later, Leonhard Euler, with no knowledge of Remond de Montmort’s work, revisited it in 1779. Euler presented methods of recursion to solve derangement problems. Euler familiarized the mathematical community with derangements, and he posed the following problem to illustrate the topic: Given any series of n letters a, b, c, d, e, etc., how many ways can they be rearranged such that no letter is in its original position?

2

What are Derangements?

Derangements are permutations of a set of elements in which no element remains in its original position. Any permutation of Sn = {1, 2, 3, · · · n} that has no fixed points is a derangement of Sn .

2.1

Scenario

There are three kids, each with a different Pokemon card. Each kid wants to give away their Pokemon card and get a different card in return. How many possible ways can this happen? 1

In essence, this problem asks to find the number of derangements for three elements. Let Kid 1 have Card A, Kid 2 have Card B, and Kid 3 have Card C. Let us denote this as {A, B, C}.

What are all the possible permutations? We can list them: {A, B, C} {A, C, B} {B, A, C} {B, C, A} {C, A, B} {C, B, A} There are a total of 6 permutations. How many of these are derangements? {B, C, A} {C, A, B} There are only 2 derangements. Thus, the two possibilities are: 1) Kid 1 gets Card B, Kid 2 gets Card C, and Kid 3 gets Card A 2) Kid 1 gets Card C, Kid 2 gets Card A, and Kid 3 gets Card B

3

Methodologies

In the previous example, there were only three objects for which the derangements were being counted. It clearly becomes much more involved to count them when n increases. Multiple techniques have been developed to count derangements.s The notation for the number of derangements of n elements is ! n. (The symbol lover Euler used the notation Π(n) to represent the number of derangements of n objects).

3.1

Using PIE

A common way to count derangements is using the principle of inclusion-exclusion (PIE). PIE is a systematic way to account for overcounting and undercounting in overlapping sets. Let us denote Fk as the number of permutations in which k elements are fixed, and let us denote. Recall that ! n is the number of derangements of n elements. (All derangement numbers (! n) are also known as subfactorial numbers. The function y =! x is called the subfactorial function.) To start with, we will consider all possible permutations. Then, we will subtract all the permutations in which exactly 1 element is fixed (same position). Then, we will add all the permutations in which exactly 2 elements are fixed. Then, we will subtract all the 2

 n permutations in which exactly 3 elements are fixed, and so on. There are different cases 1  n where 1 element is fixed, 2 different cases where 2 elements are fixed, and so on. For Fk , we just have to permute n − k elements and keep k fixed. Thus, Fk = (n −