Tuesday, July 16, 2013

[karzmheq] Subpermutations

Place 4 points in a square and draw a path between them, visiting every point exactly 0 or 1 times.  There are 65 possible such paths, including the degenerate paths of no points and 1 point only.  Consider it an alphabet, each letter writable without taking the pen off the paper.

Sequence is 1 2 5 16 65... http://oeis.org/A000522

f(n)=sum(i=0,n,binomial(n,i)*i!)

For larger grids, omit paths which pass through points without actually visiting them.

Inspired by Android pattern unlock.

No comments :