Tarotoast’s Stuff

Given permutations π and σ, a breakpoint between π and σ is defined as a pair of adjacent elements π_i and π_i+1 in π that are separated in σ. For example, if π = 143256 and σ = 123465, then π₁ = 1 and π₂= 4 in π form a breakpoint between π and σ since 1 and 4 are separated in σ. The number of breakpoints between π=01432567 and σ=01234567 is three (14, 25 and 67), while the number of breakpoints between σ and π is also three (12, 46 and 57).

Prove that the number of breakpoints between π and σ equals the number of breakpoints between σ and π.

Suppose there are n characters in π and σ. There are exactly n-1 adjacent pairs in them:

(π₁, π₂), (π₂, π₃), … , (π_n-1, π_n) with total of n-1 pairs, and same for σ₁ to σ_n.

Between π and σ, the number of breakpoints are number of pairs of (π_i, π_i+1) do not exist in all possible (σ_j, σ_j+1) or (σ_j, σ_j-1). Assume there are k (k < n-1) breakpoints. That is the same as saying among n-1 adjacent pairs, there are k pairs found in π but not found in σ. However, it also means there are n-1-k pairs both found in π and σ. With this knowledge, we can look at the number of breakpoints between σ and π.

There are also n-1 adjacent pairs in (σ₁, σ₂), (σ₂, σ₃), … , (σ_n-1, σ_n). We know that n-1-k pairs are found in both π and σ. That leaves the number of breakpoints between σ and π: (n-1) – (n-1-k) = k. Therefore number of breakpoints between π and σ equals the number of breakpoints between σ and π.

今天被 TA 叫上台解說我怎麼解這題的，當場其實有點囧。都一個禮拜前的事情，忽然間要我解釋我寫了甚麼我怎麼可能記得 XD

Tags: ucsd

This entry was posted on Friday, April 27th, 2007 at 8:04 pm and is filed under Bioinformatics, College (UCSD). You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.