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!

5 years, 9 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

problem:::::::::: 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?

- 5 years, 8 months ago

hope all these helps you :))))

- 5 years, 8 months ago

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

- 5 years, 8 months ago

there is no book specially for derangements but i am too searching it ...if i find i would surely give you link......:))

- 5 years, 8 months ago

GOD! You're the derangement man!!

- 5 years, 8 months ago

you may read:::::https://cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.pdf........but i think they are much higher....

- 5 years, 8 months ago

- 5 years, 8 months ago

YOU MAY READ::::http://www.math.umn.edu/~musiker/4707/Derange.pdf.....i think these are also higher....

- 5 years, 8 months ago

go through this website:::::::http://abhayavachat.blogspot.in/2011/01/derangement.html

- 5 years, 8 months ago

here is a derangement problem discussion:::::::http://math.stackexchange.com/questions/334755/derangement-problem

- 5 years, 8 months ago

here is some higher i.e. critical theorem ::::::::http://www.lix.polytechnique.fr/~liberti/pretty_structures/pdf/pcameron-ps11.pdf

- 5 years, 8 months ago

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

- 5 years, 8 months ago

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

- 5 years, 8 months ago

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}.

- 5 years, 8 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?

- 5 years, 8 months ago

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.....:)

- 5 years, 8 months ago

WAIT .... I AM GIVING YOU SOME MORE PROBLEMS AND SOLUTIONS......

- 5 years, 8 months ago

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

- 5 years, 8 months ago

(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.......:)))

- 5 years, 8 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.pdf

- 5 years, 8 months ago

yes i quoted from that pdf.... i did not dare to suggest the pdf as he was a beginner..:))

- 5 years, 8 months ago

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.

- 5 years, 8 months ago

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.

- 5 years, 8 months ago

@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..

- 5 years, 8 months ago

Thanks for the help Soham!

- 5 years, 8 months ago