A131519

[koh]

----- Original Message ----- 
From: "Max Alekseyev" <maxale at gmail.com>
To: "koh" <zbi74583 at boat.zero.ad.jp>
Cc: <seqfan at ext.jussieu.fr>
Sent: Monday, November 26, 2007 7:07 PM
Subject: Re: A131519


> On Nov 19, 2007 8:41 PM, koh <zbi74583 at boat.zero.ad.jp> wrote:
> 
>>     My early result a(3)=66 and yours 46 seem to be incorrect.
> 
> I've already rejected the value 46 as incorrect in my previous email
> on this topic.
> Below I will argue that you overcounted a(3) by 4 and the correct
> value is a(3)=58.
> 

    I agree with you.

>>     I list all parrtitions.
>>     I classified them with length of the paths.
>>
>>          G_3
>>
>>          [Names of nodes and  edges]
>>
>>          x   y   z     t_1=xy , t_2=yz
>>          o===o===o     b_1=xy , b_2=yz
>>
>>
>>          [Example of figure]
>>
>>          path b_1,t_2 is represented as follows
>>
>>          x   y-->z
>>          .-->.   .
>>
>>          cycle path t_1,-b_2
>>
>>          x-->.   .
>>          .<--.   .
>>
>>
>>     o {4}                                   {n} means directed path of length n
>>          x-->.-->.
>>          .<--.<--.
>>          {t or b}*{t or b}*{x or z}         last term is for starting point
>>          =2^3=8
>>
>>          .-->y-->.
>>          .<--.<--.
>>          {r or l}*{t or b}*{t or b}         r or l means number of symmetry
>>          =2^3=8
>>
>>     o {3} + {1}
>>          x-->.-->.   x   .   .
>>          .   .<--. + .-->.   .
>>          the same as {4}
>>          =8+8
> 
> I agree with the above results.
> 
>>     o {2} + {2}
>>          x-->.   .   .   y-->.
>>          .<--.   . + .   .<--.
>>          {t or b}*{t or b}*{x or z}
>>          =2^3=8
>>
>>          x-->.   .   .   .<--z
>>          .<--.   . + .   .-->.
>>          {t or b}*{t or b}
>>          =2^2=4
>>
>>          x-->.-->.   .   .   .
>>          .   .   . + .-->.-->.
>>          {t or b}*{t or b}*{x or z}
>>          =2^3=8
> 
> In the last subcase you have only 4 not 8 variants.
> For example, the choices of ttx and bbx coincide (as they correspond
> to a pair of parallel paths directed from x to z: one consists of
> "top" edges, the other consists of "bottom" edges).
> 

    You are right.

>>
>>     o {2} + {1} + {1}
>>          x-->.   .   .   y-->.    .   .   .
>>          .<--.   . + .   .   . +  .   .-->.
>>          {t or b}*{y or z}*{r or l}
>>          =2^3=8
> 
> Previously in this case I counted 16 variants but now I do not see
> how. It seems to me that your value 8 is correct.
> 
>>     o {1} + {1} + {1} + {1}
>>          .-->.   .   .   .<--.   .   .   .   .   .   .
>>          .   .   . + .   .   . + .-->.   . + .   .<--.
>>          =2
>>
>>     So,
>>          a(3) = 8 + 8 + 8 + 8 + 8 + 4 + 8 + 8 + 2
>>               = 62
> 
> It should be
>          a(3) = 8 + 8 + 8 + 8 + 8 + 4 + 4 + 8 + 2 = 58
> 
>>     Could you explane how to get your formula?
> 
> Below I will present an updated formula with ideas of the proof:
> 
> 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 vice
> versa), we will merge them into a single path. As a result we will
> have some partition into strokes of G_{n-1}. Therefore, we can
> consider different directions of edges x,y and different ways to
> combine them with partitions into strokes of G_{n-1}, to obtain
> partitions of G_n.
> 
> Let u(n) be the number of partitions of G_n, containing a subpath 212
> (i.e, in terms of edges: either ab or ba) not starting and ending at
> the same vertex; v(n) be the number of partitions with the edges a,b
> co-directed; w(n) be the number of partitions with a path starting and
> ending at vertex 1; and z(n) be the number of partitions containing a
> subpath 212, starting and ending at the same vertex.
> Then we have A131519(n) = u(n) + v(n) + w(n) + z(n) with u(2)=0,
> v(2)=2, w(2)=2, z(2)=2 and
> 
> u(n+1) = 2*u(n) + 4*v(n)
> v(n+1) = 6*u(n) + 3*v(n) + 4*w(n) + 2*z(n)
> w(n+1) = 2*u(n) + 2*v(n) + 4*w(n) + 2*z(n)
> z(n+1) = 2*u(n) + 4*w(n) + 4*z(n)
> 
> that implies the formula
> A131519(n) = 13*A131519(n-1) - 22*A131519(n-2) - 88*A131519(n-3) +
> 112*A131519(n-4) for n>=6.
> 
> The sequence then becomes
> 1, 6, 58, 578, 5766, 57810, 580310, 5829538, 58575686
> 

    4 terms are needed then how did you get fourth term?

    I will send to Neil an edited A131519.

    Yasutoshi