Tag Archives: factorial

Matching Tests Proof

Warning, this post uses some fierce math to prove why the pattern continues in the last post. If you want to know why the pattern continues, then welcome to the explanation.

In the last post we counted how many ways to hand student back their tests so that no student had his or her own test. This type of matching has a special name, a derangement. For a group of n students we denote the derangement as

!n

To determine this quantity we need a formula. From before, we know that !3 = 2 and !4 = 9. Now consider the general case. How many ways are there of handing back a test to the first student? We certainly can’t give him his own test. However, we could give him any of the other n – 1 tests. Let’s say we give him test i.

We could hand out the next test to anyone. Let’s consider handing it out to student i (the student with test i). We have two options. First, student i gets student 1’s test. Here is a picture:

pic 1

Once these 2 students have been assigned their tests, we have n – 2 students who still need tests. However, assigned them tests is analogous to our original problem, and we can denote this as !(n – 2).

Second, student i does not get student 1’s test. Thus, student i has 1 forbidden test. All the other students also have 1 forbidden test (namely their own test). Again, this is analogous to our original problem with n – 1 students (since we have not given student i a test yet). We can denote this as !(n – 1).

To summarize, to hand out n tests, we have the following recursive formula:

!n = (n-1)(!(n-1) + !(n-2))

We can use this formula to calculate derangements as high as we like, provided we proceed in order.

!5 = 4(!4 + !3) = 4(9 + 2) = 44

!6 = 5(!5 + !4) = 5(44 + 9) = 265

These are exactly the numerators we found when computing the fractions in the previous post!

To determine what would happen in a large class, we need a closed form for derangements. To simplify the notation for the next section, we will denote !n as D(n).

Observe the following pattern:

D(n)

D(n)-nD(n-1)

D(4) = 9

9 – 4*2 = 1

D(5) = 44

44 – 5*9 = -1

D(6) = 265

265 – 6*44 = 1

D(7) = 1854

1854 – 7*265 = -1

We can prove the above pattern continues using induction. The base case has been dealt with above. Our inductive hypothesis is:

D(n) - nD(n-1) = (-1)^n

Consider n+1:

D(n+1) - (n+1)D(n) = n(D(n)+D(n-1)) - (n+1)D(n) using the recurrence relation

= nD(n) + nD(n-1) - nD(n) - D(n)

= nD(n-1) - D(n)

= -(D(n) - nD(n-1))

= -(-1)^n by the inductive hypothesis

= (-1)^{n+1}

Using this information, we have a new recurrence relation for D(n):

D(n) = nD(n-1) + (-1)^n

Unfortunately, this is still not a closed form solution. However, we will use induction again to get us the rest of the way. The following is the closed form solution for D(n):

D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!} = n! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)

Checking the OEIS, we find that D(0) = 1 and D(1) = 0. Using the formula for D(3), we can see that the base case will hold:

D(3) = 3! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} \right)

= 6 \left( 1 -1 + \frac{1}{2} - \frac{1}{6} \right)

= 6 \left(\frac{3}{6} - \frac{1}{6} \right)

= 6 \left(\frac{2}{6} \right)

D(3) = 2 as expected.

Suppose the formula is true for D(n). Consider D(n+1):

D(n+1)= (n+1)D(n) + (-1)^{n+1} from the new recursive formula

= (n+1)n!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1} using the inductive hypothesis

= (n+1)!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1} definition of factorial

= (n+1)!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1} \frac{(n+1)!}{(n+1)!}

= (n+1)! \left[ \sum_{k=0}^n\frac{(-1)^k}{k!} + \frac{(-1)^{n+1}}{(n+1)!} \right]

= (n+1)! \sum_{k=0}^{n+1}\frac{(-1)^k}{k!}

Thus, the formula is true for any n. This formula is closed, but complicated. The last step in the process is to relate derangements to our original problem. Since we were looking for a probability, we were really interested in \frac{D(n)}{n!}. Using the Taylor series approximation for e-1 we get the following:

\frac{D(n)}{n!} = n! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) \frac{1}{n!}

= \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)

\approx e^{-1}

Finally! We have our answer! Since the number of students determines how many terms of the sequence for e we use, the approximation is valid for even small classes of only 10 or 15 students. The probability of handing out tests properly is approximately e^{-1} = \frac{1}{e} = \frac{1}{2.71828} \approx 37\%

1 Comment

Filed under Uncategorized