Waste less time on Facebook — follow Brilliant.
×

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
4 years, 3 months ago

No vote yet
5 votes

Comments

Sort by:

Top Newest

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? Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Raja Metronetizen hope all these helps you :)))) Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Raja Metronetizen Thank you! Can you suggest a book in which this can be studied? Vikram Waradpande · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande hope reading all these 10 articles would make you matured in derangements.....:--))* Raja Metronetizen · 4 years, 3 months ago

Log in to reply

Log in to reply

@Vikram Waradpande 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 Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande here is some higher i.e. critical theorem ::::::::http://www.lix.polytechnique.fr/~liberti/pretty_structures/pdf/pcameron-ps11.pdf Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande here is a derangement problem discussion:::::::http://math.stackexchange.com/questions/334755/derangement-problem Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande go through this website:::::::http://abhayavachat.blogspot.in/2011/01/derangement.html Raja Metronetizen · 4 years, 3 months ago

Log in to reply

Log in to reply

@Vikram Waradpande YOU MAY READ::::http://www.math.umn.edu/~musiker/4707/Derange.pdf.....i think these are also higher.... Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande you may read::::::http://mathworld.wolfram.com/Derangement.html...............THIS WEBSITE[WOLFRAM IS ACTUALLY KING MATH ARTICLE OF INTERNET] MAY HELP YOU A LOT......... Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Vikram Waradpande you may read:::::https://cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.pdf........but i think they are much higher.... Raja Metronetizen · 4 years, 3 months ago

Log in to reply

Log in to reply

@Vikram Waradpande there is no book specially for derangements but i am too searching it ...if i find i would surely give you link......:)) Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Raja Metronetizen GOD! You're the derangement man!! Soham Chanda · 4 years, 3 months ago

Log in to reply

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}. Samuel Li · 4 years, 3 months ago

Log in to reply

@Samuel Li Thank You! But all i wanna know is this same example with n members in the set. Can you please help me out? Vikram Waradpande · 4 years, 3 months ago

Log in to reply

@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.. Soham Chanda · 4 years, 3 months ago

Log in to reply

@Soham Chanda Thanks for the help Soham! Vikram Waradpande · 4 years, 3 months ago

Log in to reply

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 Metronetizen · 4 years, 3 months ago

Log in to reply

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. Raja Metronetizen · 4 years, 3 months ago

Log in to reply

(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.......:))) Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Raja Metronetizen 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 Samuel Li · 4 years, 3 months ago

Log in to reply

@Samuel Li yes i quoted from that pdf.... i did not dare to suggest the pdf as he was a beginner..:)) Raja Metronetizen · 4 years, 3 months ago

Log in to reply

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 Raja Metronetizen · 4 years, 3 months ago

Log in to reply

WAIT .... I AM GIVING YOU SOME MORE PROBLEMS AND SOLUTIONS...... Raja Metronetizen · 4 years, 3 months ago

Log in to reply

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.....:) Raja Metronetizen · 4 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...