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!

## Comments

Sort by:

TopNewestproblem:::::::::: There are 15 students in classroom. The teacher is not satisﬁed with the seating arrangement and demands that everyone move to a new seat. How many new conﬁgurations are possible? – Raja Metronetizen · 4 years, 3 months ago

Log in to reply

– Raja Metronetizen · 4 years, 3 months ago

hope all these helps you :))))Log in to reply

– Vikram Waradpande · 4 years, 3 months ago

Thank you! Can you suggest a book in which this can be studied?Log in to reply

– Raja Metronetizen · 4 years, 3 months ago

hope reading all these 10 articles would make you matured in derangements.....:--))*Log in to reply

http://www.jamestanton.com/wp-content/uploads/2010/12/derangements-essay2.pdf – Raja Metronetizen · 4 years, 3 months ago

here a easy reading material:::Log in to reply

http://www.askiitians.com/iit-jee-algebra/permutations-and-combinations/derangements-and-multinomial-theorem.aspx – Raja Metronetizen · 4 years, 3 months ago

here you can find relation between derangement and multinomial theorem:::::Log in to reply

http://www.lix.polytechnique.fr/~liberti/pretty_structures/pdf/pcameron-ps11.pdf – Raja Metronetizen · 4 years, 3 months ago

here is some higher i.e. critical theorem ::::::::Log in to reply

http://math.stackexchange.com/questions/334755/derangement-problem – Raja Metronetizen · 4 years, 3 months ago

here is a derangement problem discussion:::::::Log in to reply

http://abhayavachat.blogspot.in/2011/01/derangement.html – Raja Metronetizen · 4 years, 3 months ago

go through this website:::::::Log in to reply

http://math.illinoisstate.edu/day/courses/old/305/contentderangements.html – Raja Metronetizen · 4 years, 3 months ago

go through this website:::::Log in to reply

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

YOU MAY READ::::Log in to reply

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

you may read::::::Log in to reply

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

you may read:::::Log in to reply

http://math.ucr.edu/home/baez/qg-winter2004/derangement.pdf – Raja Metronetizen · 4 years, 3 months ago

you may read:::Log in to reply

– Raja Metronetizen · 4 years, 3 months ago

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

– Soham Chanda · 4 years, 3 months ago

GOD! You're the derangement man!!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

– Vikram Waradpande · 4 years, 3 months ago

Thank You! But all i wanna know is this same example with n members in the set. Can you please help me out?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

– Vikram Waradpande · 4 years, 3 months ago

Thanks for the help Soham!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 ﬁfteen 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 ﬁfteen 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 ﬁve 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, ﬁrst 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 ﬁnd 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

– Samuel Li · 4 years, 3 months ago

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.pdfLog in to reply

– Raja Metronetizen · 4 years, 3 months ago

yes i quoted from that pdf.... i did not dare to suggest the pdf as he was a beginner..:))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