A131709

[koh]

    Max wrote : 




>>     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.
> 
> Construction of such a partition can be done as follows:
> 
> 1) For every vertex v in the graph define a maximum matching on the
> incident edges, maybe leaving one edge unmatched (if the degree d of v
> is odd), and replace v and the incident edges with floor(d/2) copies
> of v on connected pairs of matched edges and possibly one (if d is
> odd) copy of v as an endpoint of the unmatched edge.
> 
> E.g., for vertex v with three incident edges A=(a,v), B=(b,v),
> C=(c,v), a maximum matching {(A,B),C} will result in edges (a,v1),
> (v1,b), (c,v2) where v1 and v2 are copies of v.
> 
> Note that there total number of maximum matchings for a vertex v of degree d is
> d! / 2^floor(d/2) / floor(d/2)!
> 
> 2) Described transformation results in a decomposition of the original
> graph into paths and cycles where no two paths share an endpoint. For
> every cycle we need to choose one vertex different from endpoints of
> the paths and from vertices chosen in other cycles (here "different"
> means that vertices are not copies of the same vertex from the
> original graph), and cut the cycle at the chosen vertex into a
> "circular" path (whose endpoints coincide with the chosen vertex).
> 
> As the result we will have a partition of the graph into undirected
> strokes as defined above. Moreover, every such partition can be
> obtained this way.
> 
    I have understood almost about your method. 
    I think the way of graph theorist is smart.

    I got the following formula.

    a(n) = Product_{v_i} m_i
         + Sum_{c_j} (se_j - 1)*Product_{v_k E (G_n-c_j)} m_k
          where : 
                v_i E V_n, G_n={V_n,E_n}, "E" means element
                m_i means number of matching of incident edges of v_i
                c_j means cycles in G_n
                se_j means number of start-end points in c_j
                v_k E G_n and not(v_k E c_j)
                m_k means number of matching of incident edges of v_k


        ._._._.     n=3
　　　　|_|_|_|

    a(3)
    = 3^4 + 2*3^2 - 1 + 2+ 3 + 3
    = 81 + 18 + 7
    = 106

        ._._._._.   n=4
　　　　|_|_|_|_|

    a(4)
    = 3^6 + 2*3^4 - 2*3^2 + 2*3^2 - 1 + 2*1 + 3*3^2 + 2*1 + 2*3 + 3
    = 729 + 162 + 1 + 27 + 11
    = 930


    S : 1,4,14,106,930
    


> I've got the following general formula:
> 
> For n>=2, S(n) = 3^(2*(n-1)) + 3^(n-1) + 2 + (3^n + 27 - 18*n)/4
> 
> S : 1, 4, 14, 92, 767, 6689, 59456, 532694, 4786769, 43058171,
> 387454898, 3486887696, 31381369571, 282430466453, 2541868618340
> 
> Regards,
> Max

    The terms for n=3,4 are different.

    Which are correct?    

  
    My early result by hand for n=3 is the following.
    I might have lost some, because it is also different from 106.


    I list all partitions with their figures.

         ._._._.
         |_|_|_|


         ._._._.
         |_._|_| +   |            12
         ._. ._.      _
         |_|_|_| +                8
         ._._._.
         |_| ._| +   ._|          8
         ._._._.
         |_._._| +   | |          4
         ._._.      _.
         |_|_|   +  _|            12
         ._. ._.   ._.
         |_._._| + | |            2
         ._._.     ._.
         |_| |  + _._|            8
         ._._.            _.
         |_._|  +  |  +   _|      4
         ._.       ._._.
         |_|_   +    |_|          8
         ._.       _     ._.
         |_|_   +     +  |_|      16
         ._.            _._.
         |_|    +  _| +   _|      8
         ._.       _    ._.
         |_|    +  _  + |_|       4
         ._.       _.    _.
         |_|    +  _| +  _|       4
    

    So, S(3)=98 .
    


    To Neil : 

    The figures of A131709 are ugly.


    Yasutoshi



> The figures of A131709 are ugly

Yes!  I will fix them - thanks for pointing this out

Neil