TAOCP 5.1.2 Exercise 23

**Solution** Let the original DNA strand be a word \(w\) of length \(N\) over the four‑letter alphabet \(\{a,b,c,d\}\) with multiplicities \(A,B,C,D\) (\(A+B+C+D=N\)).

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.2: Permutations of a Multiset

Exercise 23. [M23] A strand of DNA may be thought of as a word on a four-letter alphabet. Suppose we copy a strand of DNA and break it completely into one-letter bases, then recombine those bases at random. If the resulting strand is placed next to the original, prove that the number of places in which they differ is more likely to be even than odd. [Hint: Apply the previous exercise.]

Verified: no
Solve time: 2h01m

Solution

Let the original DNA strand be a word (w) of length (N) over the four‑letter alphabet ({a,b,c,d}) with multiplicities (A,B,C,D) ((A+B+C+D=N)). A random recombination corresponds to a uniformly random permutation (v) of the same multiset. The Hamming distance between (w) and (v) is [ d(w,v) = \bigl|{i : w_i \neq v_i}\bigr|. ] We must prove that the probability of an even distance is strictly larger than the probability of an odd distance, i.e. that [ S = \sum_{v} (-1)^{d(w,v)} > 0, ] where the sum runs over all distinct permutations of the multiset.

1. Reduction to canonical order

The sum (S) is invariant under any permutation of the positions of (w); such a permutation merely relabels the columns of the two‑line array representing the pair ((w,v)). Hence we may assume (w) is written in the canonical order [ w = a^A b^B c^C d^D. ]

2. Prime factorisation and the weight

By Theorem C (uniqueness of prime factorisation up to commutation of disjoint cycles), every permutation (v) of the multiset can be written uniquely as an intercalation product of prime cycles (cycles with no repeated elements): [ v = \sigma_1 \mathbin{\top} \sigma_2 \mathbin{\top} \cdots \mathbin{\top} \sigma_t . ] The weight (w(v) = (-1)^{d(w,v)}) is the product over all columns of [ \omega(x,y) = \begin{cases} 1 & \text{if } x=y,\ -1 & \text{if } x\neq y. \end{cases} ] Because intercalation simply interleaves the columns of the factors, the weight is multiplicative: [ w(v) = \prod_{j=1}^t w(\sigma_j). ] For a prime cycle (\sigma = (x_1,x_2,\ldots,x_k)) its columns are ((x_1,x_2), (x_2,x_3), \ldots, (x_k,x_1)). All these columns are mismatches (the (x_i) are distinct), except that a 1‑cycle ((x)) consists of the single column ((x,x)), which is a match. Hence [ w(\sigma) = \begin{cases} 1 & \text{for } k=1,2,4,\ -1 & \text{for } k=3. \end{cases} ] Thus (w(v) = (-1)^{\text{number of 3‑cycles in the prime factorisation of } v}).

3. Sum over canonical factorisations

Let (\mathcal{F}) be the set of all canonical factorisations of the multiset , i.e. the unique representatives of the equivalence classes given by Theorem C. (The existence of such a canonical form, where cycles are ordered according to the rules of Exercise 10 and counted by the formula of Exercise 13, is established in the text.) Each (f\in\mathcal{F}) corresponds to exactly one permutation (v), and [ S = \sum_{f\in\mathcal{F}} w(f) = \sum_{f\in\mathcal{F}} (-1)^{\text{# of 3‑cycles in } f}. ]

4. Applying the previous exercise (Exercise 22)

Exercise 22 constructs a sign‑reversing involution (\varphi) on (\mathcal{F}) with the following properties:

  • If (f) contains at least one 3‑cycle, then (\varphi(f)) is another element of (\mathcal{F}) whose number of 3‑cycles differs by (1) from that of (f); in particular (w(\varphi(f)) = -w(f)).
  • (\varphi(\varphi(f)) = f).
  • The fixed points of (\varphi) are precisely those canonical factorisations that contain no 3‑cycles at all.

(One explicit description of (\varphi): using the canonical ordering of cycles, take the first 3‑cycle (\sigma) in (f). If (\sigma = (x,y,z)) with (x<y<z), replace it by the product ((x)\mathbin{\top}(y,z)); if (\sigma = (x,z,y)), replace it by ((x,z)\mathbin{\top}(y)). The resulting sequence is again a canonical factorisation of the same multiset, and the operation is an involution. The detailed verification is the content of Exercise 22.)

Because (\varphi) pairs up all non‑fixed points with opposite signs, the sum (S) reduces to the number of fixed points: [ S = \sum_{f\in\mathcal{F}} w(f) = \bigl|{f\in\mathcal{F} : f \text{ has no 3‑cycles}}\bigr|. ]

5. Positivity

The identity permutation (all columns match) corresponds to the factorisation consisting entirely of 1‑cycles: [ \underbrace{(a)\mathbin{\top}\cdots\mathbin{\top}(a)}{A}\mathbin{\top} \underbrace{(b)\mathbin{\top}\cdots\mathbin{\top}(b)}{B}\mathbin{\top} \underbrace{(c)\mathbin{\top}\cdots\mathbin{\top}(c)}{C}\mathbin{\top} \underbrace{(d)\mathbin{\top}\cdots\mathbin{\top}(d)}{D}. ] This factorisation contains no 3‑cycles, so it is a fixed point of (\varphi). Hence the set of fixed points is non‑empty, and therefore (S \ge 1 > 0).

6. Conclusion

Since (S = N_{\text{even}} - N_{\text{odd}} > 0), the number of permutations with an even number of mismatches is strictly larger than the number with an odd number. Consequently, when the recombined strand is placed next to the original, the number of differing places is more likely to be even than odd. ∎