Word Derangements and ArrangementsDate: 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/ Date: 09/14/2017 at 14:41:06 From: Thayer Subject: "Physical" meaning of terms in Inclusion-Exclusion for n=4 I understand that the inclusion-exclusion formula for n = 4 gives the proper 9 derangements. But I don't understand the meaning of the terms when applied to the set {1, 2, 3, 4}. In particular, I can't figure out the actual arrangements in its terms. Put another way: The number of derangements with 3 fixed elements is 4C3*1! = 4. But if 3 elements are fixed, there is only one choice for the 4th element. What are the 4 derangements of {1234} that have three elements fixed? Isn't there only one -- namely, 1234? Date: 09/14/2017 at 21:06:46 From: Doctor Peterson Subject: Re: Hi, Thayer. I suppose you are referring to a variation of the formula above: D(n) = n! - n!/1! + n!/2! - n!/3! + n!/4! - ... + (-1)^n*n!/n! Your version, though you didn't state it, is the unsimplified form of the same formula. In your case, n = 4, and we have D(4) = 4! - 4!/1! + 4!/2! - 4!/3! + 4!/4! = 24 - 24 + 12 - 4 + 1 = 9 The first term is the total number of possible arrangements; the second is the number of those with some one element fixed (i.e., A fixed, or B fixed, or C fixed, or D fixed, so that those with at least two fixed are counted twice); the next is the number of those with some pair of elements fixed (AB, AC, AD, BC, BD, or CD), and so on. Let's make a table showing the arrangements counted in each term. To avoid confusing an element with a number of elements, I'm going to use letters (ABCD) rather than digits (1234). This also lets me put an element in lower case when it is in its place, to make them easy to see. # fixed --> 1 | 2 | 3 | 4 ------------------- ----------------------------- ------- ----- all| A B C D AB AC AD BC BD CD ---- ---- ---- ---- ---- |---- ---- ---- ---- ---- ----|-------|----- abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd*4 abcd abDC abDC abDC abDC aCBd aCBd aCBd aCBd aCDB aCDB aDBC aDBC aDcB aDcB aDcB aDcB BAcd BAcd BAcd BAcd BADC BCAd BCAd BCDA BDAC BDcA BDcA CABd CABd CADB CbAd CbAd CbAd CbAd CbDA CbDA CDAB CDBA DABC DAcB DAcB DbAC DbAC DbcA DbcA DbcA DbcA DCAB DCBA ---- ---- ---- ---- ---- |---- ---- ---- ---- ---- ----|-------| ---- 24 6 6 6 6 2 2 2 2 2 2 4 1 ---- ------------------- |-----------------------------|-------| ---- 24 24 12 4 1 The main idea is that when we say we are counting "arrangements with one object fixed," what we really mean is "arrangements with x fixed, for each possible x." This counts many arrangements twice, so we have to subtract those duplicates. In the column above that enumerates 3 fixed arrangements, abcd is counted four times (once each for ABC, ABD, ACD, and BCD), which I didn't bother breaking out into four sub-columns. This is what you were specifically asking about: yes, there is only one such arrangement. But we count it four times, once for each possible choice of 3. I liked your idea of listing everything explicitly, which is why I wrote more than just the one paragraph above. A table does make the whole idea a lot clearer. What do you think? - Doctor Peterson, The Math Forum at NCTM http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/