##
Non-Backtracking Pathways

Posted by Donatello under

Biological
Leave a Comment
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…

### Like this:

Like Loading...

*Related*

## Leave a Reply