The menages problem poses the following question. Some consider it to be desirable that menand women alternate when seated at a circular table. If n couples are seated randomly according tothis rule, show that the probability that nobody sits next to his or her partner is1n!Xnk=0(1)k 2n2n k

2n k

k!(n k)!You may find it useful to show first that the number of ways of selecting k non-overlapping pairs ofadjacent seats is