Derangements.
I've been studying elementary combinatorics from a couple of days. I've covered topics like Permutations and Combinations, Principle of Inclusion-Exclusion, and some problems dealing with those concepts. Today I read about derangements and i'm not quite getting it. Can someone please explain to me it in short and a suitable small example? Thank You!
Note by
Vikram Waradpande
8 years, 1 month ago
No vote yet
5 votes
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
problem:::::::::: There are 15 students in classroom. The teacher is not satisfied with the seating arrangement and demands that everyone move to a new seat. How many new configurations are possible?
Log in to reply
hope all these helps you :))))
Log in to reply
Thank you! Can you suggest a book in which this can be studied?
Log in to reply
there is no book specially for derangements but i am too searching it ...if i find i would surely give you link......:))
Log in to reply
GOD! You're the derangement man!!
you may read:::http://math.ucr.edu/home/baez/qg-winter2004/derangement.pdf
you may read:::::https://cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.pdf........but i think they are much higher....
you may read::::::http://mathworld.wolfram.com/Derangement.html...............THIS WEBSITE[WOLFRAM IS ACTUALLY KING MATH ARTICLE OF INTERNET] MAY HELP YOU A LOT.........
YOU MAY READ::::http://www.math.umn.edu/~musiker/4707/Derange.pdf.....i think these are also higher....
go through this website:::::http://math.illinoisstate.edu/day/courses/old/305/contentderangements.html
go through this website:::::::http://abhayavachat.blogspot.in/2011/01/derangement.html
here is a derangement problem discussion:::::::http://math.stackexchange.com/questions/334755/derangement-problem
here is some higher i.e. critical theorem ::::::::http://www.lix.polytechnique.fr/~liberti/pretty_structures/pdf/pcameron-ps11.pdf
here you can find relation between derangement and multinomial theorem:::::http://www.askiitians.com/iit-jee-algebra/permutations-and-combinations/derangements-and-multinomial-theorem.aspx
here a easy reading material:::http://www.jamestanton.com/wp-content/uploads/2010/12/derangements-essay2.pdf
hope reading all these 10 articles would make you matured in derangements.....:--))*
Derangements are the number of ways to arrange a given set to satisfy certain criteria. An example of a set would be {1,2,3}. To be a derangement of the set, each member of the set has to be in a different place than it started. For example. {2,1,3} is not a derangement because the 3 is in the same place as before. However, {3,1,2} is a derangement because all the members are in different spots. In this case, there are only 2 derangements: {3,1,2} and {2,3,1}.
Log in to reply
Thank You! But all i wanna know is this same example with n members in the set. Can you please help me out?
think of a small problem: let you have a bunch of letters where there is 29 letters and you have also 29 envelopes .....but as you do not have the exact right address of each letter you are putting letters arbitrarily in those envelopes....the question is ::: in how many ways how can you put atleast 15 letters in their corresponding right envelopes..... try to answer this question at first... it is one type of derangement problem...HOPE THIS HELPS.....:)
WAIT .... I AM GIVING YOU SOME MORE PROBLEMS AND SOLUTIONS......
Given n letters and n addressed envelopes, in how many ways can the letters be placed in the envelopes so that no letter is in the correct envelope? Solve this problem for the special cases n = 3, n = 4, and n = 5
(n = 3) There are 3! = 6 total ways in which the letters can be placed in envelopes, namely (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). Of these, only (2,3,1) and (3,1,2) are derangements, so there are 2 derangements of three letters. The proportion of placements that are derangements is 2/3! = 1/3. (n = 4) There are 4! = 24 total ways in which the four letters can be placed in four envelopes. The derangements are (2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), and (4,3,2,1). So there are 9 derangements of four letters. The proportion of placements that are derangements is 9/4! = 3/8. (n = 5) For n = 5, let’s adopt a more clever technique. Let d(n) denote the number of derangements of n letters. To construct a derangement of n letters, first choose k with 2 ≤ k ≤ n, and place letter k in envelope 1. Then letter 1 is either placed in envelope k or not. If letter 1 is placed in envelope k, then we complete our derangement by choosing any derangement of {2,3, . . . , k −1, k + 1, . . . , n}, which can be done in d(n−2) ways. If letter 1 is not placed in envelope k, then we can choose a derangement of {2,3, . . . , n}, and replace k with 1. This can be done in d(n − 1) ways. So d(n) = (n − 1)(d(n − 1) + d(n − 2)). For n = 5, we find that d(5) = 4(d(4) + d(3)) = 4(9 + 2) = 44. The proportion of placements that are derangements is 44/5! = 11/30...................HAPPY PROBLEM SOLVING OF DERANGEMENTS.......:)))
Log in to reply
The above solution is from Math 108 Combinatorics Fall 2005 Homework 1 Solutions, and you should read the pdf for extra explanations. There are some nice problems in there. http://math.stanford.edu/~thiem/courses/108S/hw1solns.pdf
Log in to reply
yes i quoted from that pdf.... i did not dare to suggest the pdf as he was a beginner..:))
ANOTHER PROBLEM:::Fifteen schoolgirls walk each day in five groups of three. Arrange the girls’ walks for a week so that, in that time, each pair of girls walks together in a group exactly once. Solve this problem for nine schoolgirls walking for four days.
HERE IS THE SOLUTION::::::::::: The following arrangement gives one solution for nine schoolgirls: Day 1: {1,2,3}, {4,5,6}, {7,8,9} Day 2: {1,4,7}, {2,5,8}, {3,6,9} Day 3: {1,5,9}, {2,6,7}, {3,4,8} Day 4: {1,6,8}, {2,4,9}, {3,5,7} This is the unique solution up to permutations of the girls. For fifteen schoolgirls, this arrangement works: Day 1: {1,2,3}, {4,5,6}, {7,8,9}, {10,11,12}, {13,14,15} Day 2: {1,4,8}, {2,5,11}, {3,9,15}, {6,12,14}, {7,10,13} Day 3: {1,5,13}, {2,8,14}, {3,7,11}, {4,9,12}, {6,10,15} Day 4: {1,6,9}, {2,12,15}, {3,8,10}, {4,11,13}, {5,8,15} Day 5: {1,7,12}, {2,4,10}, {3,6,13}, {5,8,15}, {9,11,14} Day 6: {1,10,14}, {2,9,13}, {3,5,12}, {4,7,15}, {6,8,11} Day 7: {1,11,15}, {2,6,7}, {3,4,14}, {5,9,10}, {8,12,13} There are seven distinct solutions for fifteen schoolgirls up to permutations of the girls. Generalizations of this problem in design theory include Kirkman Triple Systems, Steiner Triple Systems, and Oberwolfach problems. In particular, suppose there are n schoolgirls who walk every day in n/3 groups of 3. For what values of n can you arrange the girls’ walks so that over some number of days, each pair of girls walks together in a group exactly once? That is equivalent to asking for the existence of a certain Kirkman Triple System. There are two obvious necessary conditions. First, n must be divisible by 3. Also, the number of days required is [nC2]/[3*(n/3)]=(n-1)/2
(this is the number of pairs of schoolgirls divided by the number of pairs of schoolgirls with a group of size 3 and the number of groups each day). Therefore n must be odd. These two conditions on n say precisely that n must be congruent to 3 modulo 6. Ray-Chaudhuri and Wilson [2] showed that there is always a solution for n congruent to 3 modulo 6.
@Raja - Slow down buddy!! He's just started combinatorics don't frighten him :P !! Btw,what you posted is really good.
@Vikram- Derangement was a bit tricky for me to learn as well,my concepts were not clear untliss i read the brilliant blog on PIE,go to the blog and search for it,hope it helps..
Log in to reply
Thanks for the help Soham!