Recall Example 3.4 in which 2n people as n couples are randomly seated around a table. There are other interesting ways of determining Pr(K = k)

without the explicit use of the De Moivre–Jordan theorem. As before, let the couples be numbered 1 to n and define events Ck = {couple k sits together}, k = 1, ... ,n. (Contributed by Walther Paravicini)

(a) Derive Pr(K = n) and Pr(K = n − 1) directly from basic principles.

(b) Derive Pr(K = 0) and Pr(K = 1) directly using Poincare’s theorem. ´

(c) Let Ck,n denote the number of ways in which k couples can be seated together when n couples are sitting around the table, so that

Instead of obtaining a closed-form expression for Ck,n, express Ck,n recursively as

where α1, ... ,α4 are functions of k and n. (If we envisage a fixed-size round table with 2n chairs as opposed to one which ‘expands as needed’, then we define a couple sitting together to be when nobody else sits between them, even if they are separated by many empty chairs.) For instance, with n − 1 couples already seated such that k + 2 pairs are sitting together, in order for couple n to seat themselves such that only k pairs result is to have the ‘husband’ sit between one of the k + 2 couples and the ‘wife’ to sit between a different pair, i.e. α4 = (k + 2) (k + 1). In addition, the ‘starting values’ C0,1, C1,1, C0,2, C1,2 and C2,2 will be required, e.g. C0,1 = 0 and C1,1 = 1.
Finally, program the algorithm for computing Pr(K = k) via the Ck,n.

(d) Let Ek be the event that couples 1 to k, and only couples 1 to k, are seated together and let Lk be the event that at least couples 1 to k are seated together. Note that Pr(Lk) is given by (3.3). Explain the formula

express it as

and show how it may be used recursively to obtain Pr(Ek). With Pr(Ek)
computable, find the relationship between Pr(K = k) and Pr(Ek).

(e) Argue that event Lk can be written as the disjoint union of Ek and

By applying Poincare’s theorem to the latter event, show

and then derive (3.4).

(f) Use the recursive formula (3.25) to verify (3.26).

Pr (K = k) = Ck.n (2n-1)!