Word Derangements and Arrangements
Date: 11/30/98 at 15:34:52 From: julie Subject: Derangements Hi Dr. Math, I have to write this paper on derangements but I'm a little stuck. First you have to find the arrangements on let's say a 3 letter word, JOE. JOE has 6 arrangements: J,O,E J,E,O O,J,E O,E,J E,J,O E,O,J. Now to find the derangements, you have to put the letters in alphabetical order, which is E J O. This means that E cannot be the 1st letter, J cannot be the 2nd letter, and O cannot be the 3rd letter. Since there are only two arrangements that meet this criterion, JOE has 2 derangements, J,O,E and O,E,J. I figured out all the derangements for 2, 3, 4, and 5 lettered words by listing them, but when I got up to the 6th lettered word, I got stuck because a 6 lettered word has 720 arrangements. It'll be impossible for me to list all the derangements. Is there a formula that I can use to find the derangements of arrangements?
Date: 11/30/98 at 17:00:38 From: Doctor Rob Subject: Re: derrangements Yes, there is. The formula is: D(n) = n! - n!/1! + n!/2! - n!/3! + n!/4! - ... + (-1)^n*n!/n! When n = 6, this gives: D(6) = 720 - 720 + 720/2 - 720/6 + 720/24 - 720/120 + 720/720 = 720 - 720 + 360 - 120 + 30 - 6 + 1 = 265 This formula is gotten by starting with the n! arrangements, then subtracting those with one object fixed, C(n,1)*(n-1)! = n!/1!, then adding those with two objects fixed, C(n,2)*(n-2)! = n!/2!, because they had been subtracted twice. Then we subtract those with three objects fixed, C(n,3)*(n-3)! = n!/3!, because they had been subtracted thrice, but added back in thrice. We continue thus until we run out of objects. A short way to compute this is to pick the closest integer to n!/e. Here e is the base of natural logarithms, 2.718281828459045.... If n = 6, this gives 720/2.718281828459045... = 264.8731976..., so D(6) = 265, the same answer we got above. The first few answers are 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, and 1334961. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Date: 12/02/98 at 17:40:36 From: julie Subject: Derangements Hello Dr. Math, I wrote to you before to ask if there was a formula to find the derangements of arrangements. You replied by sending me this formula: D(n) = n! - n!/1! + n!/2! - n!/3! + n!/4! - ......+ (-1)^n*n!/n! I understand how to use the formula, but I'm not sure how to derive it. You gave me an explanation, but it was a bit confusing. Can you please explain it again? Thank you!
Date: 12/03/98 at 10:02:41 From: Doctor Rob Subject: Re: Derangements This is an application of the Inclusion-Exclusion Principle. We want to know the number of arrangements with exactly zero items in the designated spots. That is D(n). We can count the number C(n,k) of ways to choose k spots out of n to be designated; then there are (n-k)! ways to arrange the other n-k letters. This makes a total of C(n,k)*(n-k)! = n!/k!. This is, however, more than the number of arrangements with k items in their designated spots, since some arrangements are counted more than once. We start with all the arrangements; that is, those with at least zero items in the designated spots. There are n!/0! = n! of them. From this number we subtract the number we computed above, n!/1!. This is too much to subtract, because there are arrangements with two items in their designated spots which are counted twice, once for each of the two. To compensate, we add back in the then number of arrangements with two or more items in the designated spots, namely n!/2!. But we have overcompensated, so we subtract the number of arrangements with three or more items, and so on. Example: RUST, alphabetically RSTU. There are 4! = 24 arrangements: RSTU, RSUT, RTSU, RTUS, RUST, RUTS, SRTU, SRUT, STRU, STUR, SURT, SUTR, TRSU, TRUS, TSRU, TSUR, TURS, TUSR, URST, URTS, USRT, USTR, UTRS, UTSR. There are C(4,1) = 4 ways to pick a single letter to be in its designated spot, and for each, there are (4-1)! = 3! = 6 ways to rearrange the other letters, for a total of 4*6 = 24 = 4!/1!: R fixed: RSTU, RSUT, RTSU, RTUS, RUST, RUTS S fixed: RSTU, RSUT, TSRU, TSUR, USRT, USTR T fixed: RSTU, RUTS, SRTU, SUTR, URTS, USTR U fixed: RSTU, RTSU, SRTU, STRU, TRSU, TSRU We have to discard these, but some of them appear twice (or more). To compensate, we add back in the number of arrangements with two letters in their designated spots. There are C(4,2) = 6 ways to pick two letters to be in their designated spots, and for each there are 2! = 2 ways to rearrange the other letters, for a total of 6*2 = 12 = 4!/2!: R,S fixed: RSTU, RSUT R,T fixed: RSTU, RUTS R,U fixed: RSTU, RTSU S,T fixed: RSTU, USTR S,U fixed: RSTU, TSRU T,U fixed: RSTU, SRTU Now we have overcompensated, since some arrangements with two letters fixed also have three letters fixed, so we have to subtract the number of these to compensate. There are C(4,3) = 4 ways to choose the three letters to be in their designated spots, and for each there is 1! = 1 way to rearrange the other letter, for a total of 4*1 = 4 = 4!/3!: R,S,T fixed: RSTU R,S,U fixed: RSTU R,T,U fixed: RSTU S,T,U fixed: RSTU Again, we have overcompensated, since some (actually all) arrangements with three letters fixed also have four letters fixed, so we have to add back in the number of these to compensate. There is C(4,4) = 1 way to choose the four letters to be in their designated spots, and for each there is 0! = 1 way to arrange the remaining zero letters, for a total of 1*1 = 1 = 4!/4!: R,S,T,U fixed: RSTU That makes the total: D(4) = 4!/0! - 4!/1! + 4!/2! - 4!/3! + 4!/4! = 24 - 24 + 12 - 4 + 1 = 9 The arrangement RSTU with four letters fixed was counted once in the original tally, subtracted four times, added six times, subtracted four times, then added once, for a net count of 0. There are no arrangements with exactly three letters fixed. You can verify each arrangement with exactly two letters fixed was counted once, subtracted twice, and added once, for a net count of 0. You can verify each arrangement with exactly one letter fixed was counted once, and subtracted once, for a net count of 0. All those with no letter fixed were counted once and never subtracted, for a net count of 1. For any arrangement with exactly k > 0 letters fixed, the net count is C(k,0) - C(k,1) + C(k,2) - ... = (1-1)^k = 0, by the Binomial Theorem. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.