Maximal path

[kohmoto]

    Hi, Seqfans

    I calculated "Length of maximal di-path on grid graph n x n", but it 
already existed on OEIS.
    It is A049486. 　　　　　　　　　　　　　　　　
         .__.__.__.__.
         |__|__|__|__|
         |__|__|__|__|
         |__|__|__|__|
         |__|__|__|__|

         S_0 : 0, 4, 10, 21, 34, 53,

    Then I tried to calculate  "Number of possible maximal di-paths on grid 
graph n x n"

         0 x 0
         .

         Name of node
         0

         No di-path exists. So, a(0)=0



         1 x 1
         .__.
         |__|

         Names of nodes
         12
         34

         12431
         13421
         2 di-paths exist. So, a(1)=2. Where If a di-path is a rotation of 
another one, it is not counted.



         2 x 2
         .__.__.
         |__|__|
         |__|__|

         Names of nodes
         123
         456
         789

         23698741256
         23698741258
         23698741254

         23698745214

         23698541256
         23698521456

         23658741254
         23658745214

         23654785214

         23654125896
         23654125874

         25632145896
         25632145874

         25632147854

         25698741236

         25698541236

         25896541236
         25896321456
         25896321478

         25874123698
         25874123654

         25478563214
         25478963214

         25412369874
         25412369856
         25412365896
         25412365874

         21478523698
         21478523654
         21478563254
         21478965236
         21478963256
         21478963258
         21478963254

         34 di-paths exist. So, a(2)=34.
         S_1 : 0, 2, 34

         I counted it by hand. Is it correct?
         I should write a soft ware which calculates  this sequence.


    It is essentially a problem of counting all branches of a directed tree 
graph.
    Because the union of these di-paths becomes "a tree di-graph" which 
covers a part of a grid graph.

    I understand that this description has a little ambiguousness.
    I want to know the exact mathematical term.
    How do mathematicians call the following mapping.

         eg.
         Grid graph G_1.   1 x 1 :
         .__.
         |__|

         Names of nodes
         12
         34

         Tree di-graph T_1. :
         V={a,b,c,d,e,f,g,h,i}
         E={ab,bc,cd,de,af,fg,gh,hi}

         Mapping F     T_1 -> G_1 :
         F(ab)=12, F(bc)=24, F(cd)=43, F(de)=31,
         F(af)=13, F(fg)=34, F(gh)=42, F(hi)=21

    S_0 and S_1 are a part of the study of a sequence "Number of partitions 
into strokes of grid graph n x n"
    For example, the first di-path of the case 2 x 2, "23698741256" conducts 
four partitions into strokes..
         23698741256+458
         23698741256+854
         23698741256+45+85
         23698741256+54+58

    Yasutoshi
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050923/b55f97c8/attachment.htm>