partition intostrokes

[koh]

    Max wrote : 

    > 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.
btw, if G has multiple edges, we can consider labeled and unlabeled cases. From your examples below, it follows that you consider the labeled case (where all edges are viewed as distinct).

    I think it is a better and equivalent description.

    >A131517

    I agree with you.
    I will   mail to Neil that the explanation should be written on %C line of A000079.

    >>%N A000002 Number of partitions of G_n into "strokes".
    >>                  G_n = {V_n, E_n}, V_n = {v_1, v_2}, E_n = {e_1, e_2, ….e_n}, For all {i}  e_i = v_1v_2
    >>                  Figure of G_2  : o=o    Two edges exist between v_1 and v_2 .
    >This is sequence (currently A131518) is 2*A088009(n) for odd n and 2*A088009(n) + n!*(n/2+1) for even n
The first term in this formula stands for partitions with paths starting and ending in different vertices. The second term stands for partitions with paths starting and ending at the same vertex (there are at most 2 such paths starting and ending in v_1 and v_2 respectively, and each path consists o
f even number of edges), this term exists only for even n.
It seems that your value A131518(4)=104 is incorrect. Correct value is2*25 + 4!*3 = 122. Please double check.

    I calculated it by hand as follows.
    I classified the partitions using lengths of paths.
    Name two vertices 1,2  and four edges a,b,c,d.
    o {4}
        a example : 1a2b1c2d1
        2*4!=48
    o {3}+{1} 
        a example : 1a2b1c2+1d2 
        2*4!=48
    o {2}+{2}
        a example : 1a2b1+2c1d2 
        2*4!/2!=24
    o {2}+{1}+{1}
        0
    o {1}+{1}+{1}+{1}
        a example : 1a2+1b2+1c2+1d2
        2
    So, A131518(4)=48+48+24+0+2=122 is correct.
    I made a mistake.

         
    >>%N A000003 Number of partitions of G_n into "strokes".
    >>                  G_n = {V_n, E_n}, V_n = {v_1, v_2,….v_n}, E_n = {e_1, e_2, …. e_{n-1}, f_1, f_2, …. f_{n-1}}, For all {i}  e_i = f_i = v_iv_{i+1}
    >>                  Figure of G_5 : o=o=o=o=o
    >This sequence is A131519. Please double check the value A131519(3)=66.Could you list all partitions? I've got a different value A131519(3)=46 and that this sequence satisfies the recurrent formula:A131519(n) = 9*A131519(n-1) - 10*A131519(n-2) + 8*A131519(n-3)giving the following values:1, 6, 46
, 362, 2846, 22362, ...

    Name three vertices 1,2,3 and four edges a,b,x,y  a=12, b=12, x=23, y=23
             
    o {4}
        a example : 1a2x3y2b1
        4+8+4=16
    o {3}+{1}
        a example : 1a2x3y2+1b2
        4+8+4=16
    o {2}+{2}
    a example : 1a2b1+2x3y2
    3*4=12
    o {2}+{1}+{1}
        a example : 1a2b1+2x3+2y3
        2*4=8
    o {1}+{1}+{1}+{1}
        a example : 1a2+1b2+3x2+3y2
        2
    So, A131519(3)=16+16+12+8+2=54
    My god, I got a different number from my past result and your result.
    Could you explain your formula?
    If I don't understand it then I will list all partitions in next mail.

    >A131520

    I agree with you.
    The formula is right.

    Yasutoshi