Bus route

[koh]

    Hello Seqfans.
    I considered about "Bus route problem".  

    If we made bus routes on a graph G, the roots should satisfy the following conditions.

    1. One and only one route exists on all edges of G
    2. Terminals of two different routes don't meet on the same point
    
    This definition is equivalence with "Partition of graph G into strokes" without direction.
    It is defined as follows.

    Given an undirected graph G=(V,E), its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii)union of corresponding undirected paths is E.

    So, the case of undirected paths is the following.

    Given an undirected graph G=(V,E), its partition into strokes is a collection of edge-disjoint paths (viewed as sets of edges) on V such that (i) union of any two paths is not a path; (ii)union of paths is E.


    
    I wanted to know the numbers of "Bus routes" on n x n grid graphs.
    ._._._._.    
    |_|_|_|_|    n=4
    |_|_|_|_|
    |_|_|_|_|
    |_|_|_|_|

    But it is too difficult to calculate by hand, so I count the case of 1 x n.
    ._._._._.
    |_|_|_|_|     

    S : 1,4,14,46
    off set = 0

    I wonder if no mathematician have thought this problem.

    Yasutoshi