Show that there are 127 ways to partition a set of 8 distinct elements into two non-empty subsets.
A group of 8 people ( \(\mathrm { A } , \mathrm { B } , \ldots\) ) have 8 reserved seats ( \(1,2 , \ldots\) ) on a coach. Seat 1 is reserved for person A , seat 2 for person B , and so on. The reserved seats are labelled but the individual people do not know which seat has been reserved for them.
The first 4 people, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , choose their seats at random from the 8 reserved seats.
Determine how many different arrangements there are for the seats chosen by \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .
The group organiser moves \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D to their correct seats (A in seat \(1 , \mathrm {~B}\) in seat \(2 , \mathrm { C }\) in seat 3 and D in seat 4).
The other 4 people ( \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H ) then choose their seats at random from the remaining 4 reserved seats ( \(5,6,7\) and 8 ).
List the 9 derangements of \(\{ \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } \}\), where none of these four people is in the seat that has been reserved for them.
Suppose, instead, that the 8 people had chosen their seats at random from the 8 reserved seats, without the organiser intervening.
Determine the total number of ways in which the seats can be chosen so that 4 of the people are in their correct seats and 4 are not in their correct seats.