A131519

[Max Alekseyev]

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 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).

>
>     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

Please double check.

Max