A109094 and A131709

[koh]

    Dear Artur
    I think that A109094 is interesting
    And I want to know the number of all different maximal paths in K_n.
    Because it is a part of "Bus route problem" on K_n.

    Each maximal path has partitions into rootes of subgraph {K_n - the maximal path} and they give total partitions into "Bus routes" on K_n.
    So, the number of partitions into "Bus routes" on K_n is much more than the number of maximal path in K_n.
    
    "Bus route on 1 x n grid" ---> A131709

    Once I submitted a sequence which is number of maximal directed path in 1 x n grid graph.
    But Neil rejected it.
    He seemed to think that it is not so interesting.

    A000001 is not interesting at, but A000002 is rather interesting.

    Yasutoshi


    --------------------


    %I A000001
    %S A000001 1, 4, 7, 9, 11
    %N A000001 Length of maximal path on 1 x n grid.
    %C A000001     If 1<n then a(n)=2*n+3
    %e A000001      n=4
                         .__.__.__.__.
                         |__|__|__|__|
                         Names of nodes
                         1 2 3 4 5
                         a b c d e
                         e.g.
                         345edcba123c is a maximal directed path. So,
a(4)=11
    %Y A000001 A000002, A049486
    %K A000001 none
    %O A000001 0,2
    %A A000001 Yasutsohi Kohmoto



    %I A000002
    %S A000002 2, 8, 12, 40
    %N A000002 Number of maximal directed path on 1 x n grid.
    %e A000002      n=3
                         .__.__.__.
                         |__|__|__|
                         Names of nodes
                         1 2 3 4
                         a b c d
                         Maximal directed paths which start from node 3.
                         34dcba123c
                         34dc32ba12
                         34dc321ab2
                         34dc321abc
                         3cd432ba12
                         3cd4321ab2
                         3cd4321abc
                         3cba1234dc
                         321abc34dc
                         321abcd43c
                         Paths from nodes c,b,2 exist.
                         So, n(3)=4*10=40
    %Y A000002 A000001, A089243
    %K A000002 none
    %O A000002 0,1
 
    %A A000002 Yasutoshi Kohmoto   zbi74583 at boat.zero.ad.jp


    %I A000003
    %S A000003 1,1,3,63
    %N A000003 Number of partitions into "Bus route" of K_n.
    %C A000003   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

    %Y A000002 A131709
    %K A000002 none
    %O A000002 1,3
    %A A000002 Yasutoshi Kohmoto   zbi74583 at boat.zero.ad.jp