A131709

[Max Alekseyev]

On Nov 4, 2007 5:47 PM, kohmoto <zbi74583 at boat.zero.ad.jp> wrote:

> > Yes, a(3)=104 and I suggest the following recurrent formula:
> > a(n+1) = 10*(a(n)-a(n-1)) + 4
> > giving
> > 4, 14, 104, 904, 8004, ...
> >
>     How did you get such an easy formula?
>     Could you explain about it?

I have built a mapping from partitions of a graph with n cells to
partitions of smaller graph (basically by removing one of vertical
edges). But it is hard to describe this mapping here.

> > I counted yet another way and still got a(4)=904 that agrees with the
> > recurrence above.
> > Please double check your computation of a(4).
> >
>     I seem to mistake when I count the case of two cycles.
>     I found second term shuld be 2(3^4-10).
>     So, my result is 906.
>     I counted it five times.
>
>
>     Could any other member of Seqfan tell me a exact number for a(4)?

Let me describe my way of computing a(4).
A graph with 4 cells has 3 inner vertical edges, each of which can
participate in a partition into paths and cycles in 9 different ways
(depending on 3 different matching on edges incident to the top
endpoint and 3 different matching on edges incident to the bottom
endpoint).
Let inner vertical edge v be in between of horizontal top edges x,y
(listed from left to right) and bottom edges z,t. I will ditiguish the
following ways:
"left": edges x,v,z form a subpath;
"right": edges y,v,t form a subpath;
"center": edges x,y and edges z,t form subpaths, the edge v also forms
a path on its own;
"other": neigther of above, the number of different "other" edges is 9-3=6.

A center edge is very easy to handle: its removal from the partition
of a graph results in a paritition of a graph with smaller number of
cell. By inclusion-exclusion, the number of partitions of a graph with
4 cells with at least one center edge is:
binomial(3,1)*a(3) - binomial(3,2)*a(2) + binomial(3,3)*a(1) = 3*104 -
3*14 + 4 = 274.

Now let's focus on partitions without center edges. Then every edge is
either "left" or "right", or "other" (recall, that the number of
different other edges is 6). It is important to notice that other
edges cannot be a part of a cycle.
Let consider all possible variants for the tree inner vertical edges
of the graph with 4 cells, and count the corresponding number of
partitions into strokes. I will denote "left"/"right"/"other" edges by
"l"/"r"/"o" respectively and any edge by * (there are 8 different any
edges).

lll ~ 2 (in this case we have cycle at left which can be split into
paths in two different ways)
l*r ~ 2*8*2
llo ~ 2*6
lrl ~ 0 (this is impossible case with an internal 4-cycle)
lro ~ 2*6
lol ~ 2*6
loo ~ 2*6*6
rl* ~ 0 (this is again impossible)
*rl ~ 0
rrr ~ 2
rro ~ 6
rol ~ 6
ror ~ 2*6
roo ~ 6*6
oll ~ 6
o*r ~ 6*8*2
o*o ~ 6*8*6
ool ~ 6*6

Summing up, we have
2 + 2*8*2 + 2*6 + 2*6 + 2*6 + 2*6*6 + 2 + 6 + 6 + 2*6 + 6*6 + 6 +
6*8*2 + 6*8*6 + 6*6 = 630
partitions in this case.

So, the total number of partions of the graph with 4 cells is
a(4) = 274 + 630 = 904.

Regards,
Max