A131709

[Max Alekseyev]

On 10/28/07, koh <zbi74583 at boat.zero.ad.jp> wrote:

>   I got the following formula.
>
>   a(n) = Product_{v_i} m_i
>        + Sum_{c_j} (se_j - 1)*Product_{v_k E (G_n-c_j)} m_k
>         where :
>               v_i E V_n, G_n={V_n,E_n}, "E" means element
>               m_i means number of matching of incident edges of v_i
>               c_j means cycles in G_n
>               se_j means number of start-end points in c_j
>               v_k E G_n and not(v_k E c_j)
>               m_k means number of matching of incident edges of v_k

I almost agree with your formula, except that the inner Product must
be equal 0 in some cases (when there is no way to cut the cycle, i.e.,
G_n-c_j is empty). There will be a discrepancy as the empty product is
defined as 1.

> > I've got the following general formula:
> >
> > For n>=2, S(n) = 3^(2*(n-1)) + 3^(n-1) + 2 + (3^n + 27 - 18*n)/4
> >
> > S : 1, 4, 14, 92, 767, 6689, 59456, 532694, 4786769, 43058171,
> > 387454898, 3486887696, 31381369571, 282430466453, 2541868618340

>     The terms for n=3,4 are different.
>
>     Which are correct?

I think neither one. See below.

>     My early result by hand for n=3 is the following.
>     I might have lost some, because it is also different from 106.
>
>
>     I list all partitions with their figures.
>
>          ._._._.
>          |_|_|_|
>
>
>          ._._._.
>          |_._|_| +   |            12
>          ._._._.
>          |_._._| +   | |          4

These cases are unclear. For example, the top one of the two above may
contain the bottom one as a particular case.

I suggest to count, starting with the cycle configuration (i.e., what
we have after the first step in my description of the partition
process):

1) One 8-cycle:
._._._.
|_._._|

There is an unique way to get this cycle and 4 ways to "cut" it (at
the corner vertices) into a circular path.
So, there 1*4=4 partitions here.

2) One 6-cycle:
._._.
|_._|
There are 2 ways to obtain such a cycle (either at left or at right of
the original graph) and 2 ways to cut it into a path.
So, there 2*2=4 partitions here.

3) One 4-cycle:
._.
|_|
There are 2*(3*3-1)=16 ways to obtain such a cycle (either at the left
or at the right end, but not at the middle - such a cycle cannot be
cut into a path), and there are 2 ways to cut it into a path.
So, there 16*2=32 partitions here.

4) Two 4-cycles:
._. _.
|_| |_|
There is an unique way to get such cycles and 2*2=4 ways to cut them into paths.
So, there 4 partitions here.

5) No cycles.
There are 3^4 - 2*3^2 - 2*1 - 1 + 1 = 61 (also, can be counted as
2*(3^2-1)^2 - 3 = 61) partitions here .

The total number of partitions (i.e., a(4) in A131709) is
4 + 4 + 32 + 4 + 61 = 105

This result is close to your result of 106 where you counted the
impossible case:
._    ._.  _.
|_    |_|   _|

In this case we cannot cut the inner cycle into a path. Therefore, it
does not deliver any partitions.

Neil, please do not make any corrections to A131709 until we agree
with Yasutoshi on this sequence. In particular, the latest correction
of a(4) turned it into non-sense. Please roll that correction
(together with the illustration) back to at least follow the formula
specified in the name of A131709.

Regards,
Max