Eight people are attending a seminar in a room with eight chairs. In the middle of the seminar, there is a break and everyone leaves the room.
a) In how many ways can the group sit down after the break so that no-one is in the same chair as before?
b) In how many ways can the group sit down after the break so that exactly four people are in the same chair as before?
c) In how many way can the group sit down after the break so that at least four people are in the same chair as before?
Note that your answer in each case should be an integer.
For any answer you give, describe your solution process in words.
For proofs, write out the proof as you normally would. Then, include an explanation of
your proof PRIMARILY IN WORDS. So you should have one regular proof (the kind
you see in textbooks), then another proof that describes the proof mainly in words(you
don't see this that often).
(Please see the attachment for the complete solution)
This kind of problem is known as "derangement". Let be n ordered alphabets. By definition, a derangement of these n alphabets is a permutation of A such that no alphabet in A is in its original position. Let us consider a simple example of three alphabets . It can be seen that a regular permutation of results in permutations,
( 1 )
but only and are the derangement of the original . Notice that in and , no alphabet remains in its original position.
Is there any other way much easier in finding the number of derangements? The answer is yes. Consider the previous example. The method of finding the number of derangements can be described as follows.
First: We begin with finding all possible permutations of three alphabets , which are permutations as shown in ( 1 ).
Second: We consider the case when one alphabet is fixed and the other two remaining alphabets are varied, which are ways of arranging the alphabets. Note that the first term is the number of possible ways in choosing one fixed alphabet from three possible alphabets and the second term shows the number of possible ways in rearranging the other two remaining ...
The solution deals comprehensively with each part of this derangement problem using permutations and combinations in clearly worded explanations.