Given k possible permutations for a genome of any fixed length, how many pathways are possible that traverse through these permutations from one given point to another and do not backtrack (i.e. that never go through the same point twice)?

To answer this question, we can assume a starting genome point g_a, and an endpoint g_b. The first move could be to any of the remaining genomes, except g_a and g_b. There are therefore k-2 possible locations to choose the first move.

The second move could be any of the remaining, non-chosen points, so there would be k-3 locations. Multiplying by the first move, we have (k-2)(k-3) pathways available. If we follow this pattern, we can easily see that there will be (k-2)! pathways with maximum length.

More…

Advertisements