partition into strokes

[Max Alekseyev]

On 9/7/07, koh <zbi74583 at boat.zero.ad.jp> wrote:
>> This is sequence (currently A131518) is 2*A088009(n) for odd n and2*A088009(n) + n!*(n/2+1) for even n>> The first term in this formula stands for partitions with pathsstarting and ending in different vertices. The second term stands forpartitions with paths starting and ending at the same vertex (thereare at most 2 such paths starting and ending in v_1 and v_2respectively, and each path consists of even number of edges), thisterm exists only for even n.>> It seems that your value A131518(4)=104 is incorrect. Correct valueis 2*25 + 4!*3 = 122. Please double check.
[...]
>     So, A131518(4)=48+48+24+0+2=122 is correct.
Great! I will send the formula to Neil.
>>> %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.
Oh, I've recomputed everything and got that A131519(3)=66 is correctwhile my formula from the previous email is wrong. I propose a newformula:
A131519(n) = 11*A131519(n-1) - 24*A131519(n-3) for n>3.
And the sequence is
1, 6, 66, 714, 7710, ...
>     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
It should 16 here.
>     o {2}+{1}+{1}>         a example : 1a2b1+2x3+2y3>         2*4=8
and 16 here.
>     o {1}+{1}+{1}+{1}>         a example : 1a2+1b2+3x2+3y2>         2>     So, A131519(3)=16+16+12+8+2=54
16+16+16+16+2 = 66
>     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.
Suppose that we have vertices 1,2,3,...,n and edges a=12, b=12, x=23, y=23, ...From every partition into strokes of G_n let us remove edges a,b,maybe splitting some strokes into two. Then if there appear two paths:one starting with the edge x and other ending with the edge y (or viceversa), we will merge them into a single path. As a result we willhave some partition into strokes of G_{n-1}.Therefore, we can consider different directions of edges x,y anddifferent ways to combine them with partitions into strokes ofG_{n-1}, to obtain partitions of G_n.
Let u(n) be the number partitions of G_n, containing a subpath 121(i.e, in terms of edges: either ab or ba), v(n) be the number ofpartitions with the edges a,b are both directed as (1,2), w(n) be thenumber of partitions with a path starting and ending at vertex 1, andz(n) be the number of partitions with the edges a,b are both directedas (2,1). Then we have u(2)=2, v(2)=1, w(2)=2, z(2)=1 and
u(n+1) = 4*u(n) + 4*v(n) + 4*w(n) + 4*z(n)v(n+1) = 3*u(n) + 2*v(n) + 2*w(n) + z(n)w(n+1) = 2*u(n) + 2*v(n) + 4*w(n) + 2*z(n)z(n+1) = 3*u(n) + v(n) + 2*w(n) + 2*z(n)
that implies the formula A131519(n) = 11*A131519(n-1) - 24*A131519(n-3) for n>3.
Regards,Max