Lesson Derangement problems
Algebra
->
Permutations
-> Lesson Derangement problems
Log On
Algebra: Combinatorics and Permutations
Section
Solvers
Solvers
Lessons
Lessons
Answers archive
Answers
Source code of 'Derangement problems'
This Lesson (Derangement problems)
was created by by
ikleyn(52906)
:
View Source
,
Show
About ikleyn
:
<H2>Derangement problems</H2> <H3>Problem 1</H3>Persons A, B, C and D seat in four seats 1, 2, 3, 4, in this order. How many sitting arrangements are there, in which no one of four persons seats on his chair. <B>Solution</B> <pre> Let P be the set of all sitting arrangements of A, B, C and D in four seats. As everybody knows, P consists of 4*3*2*1 = 24 permutations. Let {{{P[A]}}} be the subset of all sitting arrangements of A, B, C and D in four seats, where A is sitting in the seat #1. Let {{{P[B]}}} be the subset of all sitting arrangements of A, B, C and D in four seats, where B is sitting in the seat #2. Let {{{P[C]}}} be . . . where C is sitting in the seat #3. Let {{{P[D]}}} be . . . where D is sitting in the seat #4. Then P is, obviously, the union of subsets D + {{{P[A]}}} + {{{P[B]}}} + {{{P[C]}}} + {{{P[D]}}}, (1) where D is our most desired subset of those sitting arrangements that are under the problem's question. It is clear that the cardinality of each subset {{{P[A]}}}, {{{P[B]}}}, {{{P[C]}}} and {{{P[D]}}} is 6 = 3*2*1. Therefore, the first desire is to write 24 = |D| + 6 + 6 + 6 + 6, following (1). But it would not to be correct. Why? - Because the subsets {{{P[A]}}}, {{{P[B]}}}, {{{P[C]}}} and {{{P[D]}}} have non-empty intersections that we counted twice. Did you just get understanding on how to solve the problem and how to proceed further? If not, then follow me. Let {{{P[AB]}}} be the subset of all sitting arrangements of A, B, C and D in four seats, where A and B are sitting in the seats #1 and #2, respectively. Let {{{P[AC]}}} be the subset of all sitting arrangements of A, B, C and D in four seats, where A and C are sitting in the seats #1 and #3, respectively. Let {{{P[AD]}}}, {{{P[BC]}}}, {{{P[BD]}}} and {{{P[CD]}}} be the other four similar subsets in P. Then we can make a correction to formula (1) by writing 24 = |D| + {{{P[A]}}} + {{{P[B]}}} + {{{P[C]}}} + {{{P[D]}}} - {{{P[AB]}}} - {{{P[AC]}}} - {{{P[AD]}}} - {{{P[BC]}}} - {{{P[BD]}}} - {{{P[CD]}}} (2) in the effort to account for double intersections. But be await !! This formula is still not exactly correct. Why? - Because the sets {{{P[AB]}}}, {{{P[AC]}}}, {{{P[AD]}}}, {{{P[BC]}}}, {{{P[BD]}}} and {{{P[CD]}}} have triple intersections, which we distracted twice in the formula (2). Did you just get understanding on how to solve the problem and how to proceed further? If not, then follow me again. Let {{{P[ABC]}}} be the subset of all sitting arrangements of A, B, C and D in four seats, where A, B and C are sitting in the seats #1, #2 and #3, respectively. Let {{{P[ABD]}}} be the subset of all sitting arrangements of A, B, C and D in four seats, where A, B and D are sitting in the seats #1, #2 and #4, respectively. Let {{{P[ACD]}}} and {{{P[BCD]}}} be the other two similar subsets in P. At last, let {{{P{ABCD]}}} be the subset of all sitting arrangements of A, B, C and D in four seats, where A, B, C and D are sitting in the seats #1, #2, #3 and #4, respectively. (As you understand, the set {{{P{ABCD]}}} consists of only ONE element, the identical permutation). Now, finally, we can write the formula which is ABSOLUTELY true! : 24 = |D| + {{{P[A]}}} + {{{P[B]}}} + {{{P[C]}}} + {{{P[D]}}} - {{{P[AB]}}} - {{{P[AC]}}} - {{{P[AD]}}} - {{{P[BC]}}} - {{{P[BD]}}} - {{{P[CD]}}} + {{{P[ABC]}}} + {{{P[ABD]}}} + {{{P[ACD]}}} + {{{P[BCD]}}} - {{{P[ABCD]}}}. (3) I just mentioned above that the cardinality of the 1-letter subsets {{{P[A]}}}, {{{P[B]}}}, {{{P[C]}}} and {{{P[D]}}} is 6 = 3*2*1. The cardinality of the 2-letter subsets {{{P[AB]}}}, {{{P[AC]}}}, . . . , {{{P[CD]}}} is 2 = 2*1. Obviously. The cardinality of the 3-letter subsets {{{P[ABC]}}}, {{{P[ABD]}}}, . . . , {{{P[BCD]}}} is 1. Obviously. The cardinality of the 4-letter subsets {{{P[ABCD]}}} is 1. Obviously. Therefore, following to the formula (3), we can write its "cardinality" analogue 24 = |D| + (6 + 6 + 6 + 6) - (2 + 2 + 2 + 2 + 2 + 2) + (1 + 1 + 1 + 1) - 1 = |D| + 4*6 - 2*6 + 4 - 1 = |D| + 24 - 12 + 4 - 1 = |D| + 15. --------------- ----------------------- --------------- 4 times 6 times 4 times Again, our equation is 24 = |D| + 15. From here, the cardinality of the set D is |D| = 9. <U>ANSWER</U>. </pre> <H3>Problem 2</H3>Suppose all 6 men at a party throw their hats in the center of the room. Each man then randomly selects a hat. Find the probability that none of the 6 men selects his own hat. <B>Solution</B> <pre> In mathematical terms, the problem sounds in this way. We consider all possible permutations of 10 items. The number of all such permutations is 10! = 3628800. Then we ask ourselves : how many are there such permutations of 10 items that no one item is at its original place ? Such permutations (arrangements) are called <U>derangements</U>. About derangements, see this Wikipedia article https://en.wikipedia.org/wiki/Derangement In this article, you will find some theory about this subject and the formulas to calculate the number of derangements of n items. The formula is quite complicated, but there is a Table in this reference, containing calculated values for moderate values of n. For n= 6, the number of derangements, from this Table, is equal to 265. So, there are 6! = 720 permutations of 6 objects, in all (it is the sample space in this problem). Of them, there are 265 <U>favorable</U> derangement permutations. The probability under the problems's question is, therefore, P = {{{favorable/total}}} = {{{265/720}}} = 0.368 (approximately). <U>ANSWER</U> +---------------------------------------------------------------------------------------------------------------+ | Below I will show you the logic and the technique of getting these formulas and solving problem for n= 6. | | | | You should notice the analogy with the solution of the preceding Problem 1 of this lesson. | +---------------------------------------------------------------------------------------------------------------+ Let P be the set of all permutations of 6 items. As everybody knows, P consists of 6! = 1*2*3*4*5*6 = 720 permutations. Let {{{P[1]}}} be the subset of all permutations of 6 items, that leave item 1 on its place. Let {{{P[2]}}} be the subset of all permutations of 6 items, that leave item 2 on its place. Let {{{P[3]}}} be . . . , that leave item 3 on its place. Let {{{P[4]}}} be . . . , that leave item 4 on its place. Let {{{P[5]}}} be . . . , that leave item 5 on its place. Let {{{P[6]}}} be . . . , that leave item 6 on its place. Then P is, oviously, the union of subsets D + {{{P[1]}}} + {{{P[2]}}} + {{{P[3]}}} + {{{P[4]}}} + {{{P[5]}}} + {{{P[6]}}}, (1) where D is our most desired subset of those derangement permutations that are under the problem's question. It is clear that the cardinality of each subset {{{P[1]}}}, {{{P[2]}}}, {{{P[3]}}}, {{{P[4]}}}, {{{P[5]}}} and {{{P[6]}}} is (6-1)! = 5! = 120. Therefore, the first desire is to write 720 = |D| + 120 + 120 + 120 + 120 + 120 + 120 = P + 6*120, following (1). But it would not to be correct. Why? - Because the subsets {{{P[1]}}}, {{{P[2]}}}, {{{P[3]}}}, {{{P[4]}}}, {{{P[5]}}} and {{{P[6]}}} have non-empty intersetions that we counted twice. So, we should make correction/corrections in this formula. Let {{{P[12]}}} be the subset of all permutations of 6 items, that leave items 1 and 2 on their places. Let {{{P[13]}}} be the subset of all permutations of 6 items, that leave items 1 and 3 on their places. Let {{{P[14]}}}, {{{P[15]}}}, {{{P[16]}}}, {{{P[23]}}}, {{{P[24]}}}, . . . , {{{P[56]}}} be the other {{{C[6]^2}}} = {{{(6*5)/2}}} = 3*5 = 15 similar subsets in P. Then we can make a correction to formula (1) by writing P = D + {{{P[1]}}} + {{{P[2]}}} + . . . + {{{P[6]}}} - {{{P[12]}}} - {{{P[13]}}} - {{{P[14]}}} - . . . - {{{P[56]}}}, or P = D + 6*5! - {{{C[6]^2*(6-2)!}}} = D + {{{C[6]^1*5!}}} - {{{C[6]^2*4!}}} (2) in the effort to account for double intersections. But be await !! This formula is still not exactly correct. Why? - Because the sets {{{P[12]}}}, {{{P[13]}}}, . . . , {{{P[16]}}}, {{{P[23]}}}, {{{P[24]}}}, . . . , {{{P[56]}}} have triple intersections, which we distracted twice in the formula (2). Did you just get understanding on how to solve the problem and how to proceed further? If not, then follow me again. Let {{{P[123]}}} be the subset of all permutations of 6 items, that leave items 1, 2 and 3 on their places. Let {{{P[124]}}} be the subset of all permutations of 6 items, that leave items 1, 2 and 4 on their places. . . . . . and so on . . . Let {{{P[456]}}} be the subset of all permutations of 6 items, that leave items 4, 5 and 6 on their places. Then the next correction of the formula (2) is P = D + {{{C[6]^1*5!}}} - {{{C[6]^2*4!}}} + {{{C[6]^3*3!}}} (3) And we continue similar corrections for quadruples, quintuples and sextuples intersections. At last, let {{{P{123456]}}} be the subset of all permutations of 6 items, that leave items 1, 2, 3, 4, 5 and 6 on their places. (As you understand, the set {{{P{ABCD]}}} consists of only ONE element, the identical permutation). Now, finally, we can write the formula which is ABSOLUTELY true! : 720 = D + {{{C[6]^1*5!}}} - {{{C[6]^2*4!}}} + {{{C[6]^3*3!}}} - {{{C[6]^4*2!}}} + {{{C[6]^5*1!}}} - 1 or 720 = D + 6*120 - 15*24 + 20*6 - 15*2 + 6*1 - 1. Finally, this equation gives D = 720 - (6*120 - 15*24 + 20*6 - 15*2 + 6*1 - 1) = 265. Thus the problem is just solved, and the answer is : the number of deranged permutations of 6 items is 265. </pre> The solved problems in this lessons give you an idea on how to solve the derangement problems in general case of n items. My other lessons on Permutations and Combinations in this site are - <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Permutations.lesson>Introduction to Permutations</A> - <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-permutations.lesson>PROOF of the formula on the number of Permutations</A> - <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Permutations.lesson>Simple and simplest problems on permutations</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Special-type-permutations-problems.lesson>Special type permutations problems</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/How-many-different-permutations-may-exist-ubder-given-restrictions.lesson>Problems on Permutations with restrictions</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Permutations.lesson>Math circle level problem on Permutations</A> - <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Combinations-.lesson>Introduction to Combinations</A> - <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-combinations.lesson>PROOF of the formula on the number of Combinations</A> - <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Combinations.lesson>Problems on Combinations</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Combinations-problems-with-restrictions.lesson>Problems on Combinations with restrictions</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Combinations.lesson>Math circle level problem on Combinations</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Arranging-elements-of-sets-containing-undistinguishable-elements.lesson>Arranging elements of sets containing indistinguishable elements</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Persons-sitting-around-a-circular-table.lesson>Persons sitting around a cicular table</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Combinatoric-problems-for-entities-other-than-permutations-and-combinations.lesson>Combinatoric problems for entities other than permutations and combinations</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Fundamental-counting-principle-problems.lesson>Fundamental counting principle problems</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Miscellaneous-problems-on-permutations-combinations-and-other-combinatoric-entities.lesson>Miscellaneous problems on permutations, combinations and other combinatoric entities</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Some-twisted-combinatorics-problem.lesson>Some twisted combinatorics problem</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Inclusion-Exclusion-principle.lesson>Inclusion-Exclusion principle problems</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/In-how-many-ways-N-distinguishable-objects--can-be-distributed-among-n-different-boxes.lesson>In how many ways N distinguishable objects can be distributed among n different boxes ?</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Stars-and-bars-method-for-Combinatorics-problems-2.lesson>Stars and bars method for Combinatorics problems</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Men-and-women-standing-in-line-.lesson>Men and women standing in line</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/One-combinatorial-Geometry-problem-solved-using-the-Euler-formula.lesson>One combinatorial Geometry problem solved using the Euler formula</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/Nice-recreational-problems-on-permutations.lesson>Nice recreational problems on permutations</A> - <A HREF =https://www.algebra.com/algebra/homework/Permutations/OVERVIEW-the-lessons-on-Permutations-and-Combinations.lesson>OVERVIEW of lessons on Permutations and Combinations</A> Use this file/link <A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A> to navigate over all topics and lessons of the online textbook ALGEBRA-II.
