[seqfan] Re: Partition into Stroke

Max Alekseyev maxale at gmail.com
Fri Feb 4 22:00:34 CET 2022

Hi Yasutoshi,

Just in case, here is a proof (with correction "n>4" from "n>3") of the
formula for A131519 back from 2007.
I welcome anyone to double check it.


---------- Forwarded message ---------
From: Max Alekseyev <maxale at gmail.com>
Date: Sun, Sep 9, 2007 at 11:37 PM
Subject: Re: RE : partition into strokes
To: koh <zbi74583 at boat.zero.ad.jp>
Cc: <seqfan at ext.jussieu.fr>

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

>> This is sequence (currently A131518) is 2*A088009(n) for odd n and
2*A088009(n) + n!*(n/2+1) for even n
>> The first term in this formula stands for partitions with paths
starting and ending in different vertices. The second term stands for
partitions with paths starting and ending at the same vertex (there
are at most 2 such paths starting and ending in v_1 and v_2
respectively, and each path consists of even number of edges), this
term exists only for even n.
>> It seems that your value A131518(4)=104 is incorrect. Correct value
is 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 =
>>>                  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 correct
while my formula from the previous email is wrong. I propose a new

A131519(n) = 11*A131519(n-1) - 24*A131519(n-3) for n>4.

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,
>     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 be 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 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 partitions of G_n, containing a subpath 121
(i.e, in terms of edges: either ab or ba), v(n) be the number of
partitions with the edges a,b are both directed as (1,2), w(n) be the
number of partitions with a path starting and ending at vertex 1, and
z(n) be the number of partitions with the edges a,b are both directed
as (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


On Fri, Jan 21, 2022 at 2:12 AM <zbi74583_boat at yahoo.co.jp> wrote:

> Hi  Seqfans    I abstracted the idea of "Stroke" which is used in writing
> Kanji.    For instance, when "木" is written, which means tree, these four
> strokes are used. See " How to write a" 's page
>     https://kakijun.jp/page/0461200.html
>     My definition of " Partition into stroke " which is an abstraction of
> Kanji 's stroke is the following
>     Given an undirected graph G=(V,E), its partition into strokes is a
> collection of directed edge-disjoint paths (viewed as sets of directed
> edges) on V such that (i) union of any two paths is not a path; (ii) union
> of corresponding undirected paths is E.
>     The other description of the definition is the following
>     A "stroke" is defined as follows. If the following conditions are
> satisfied then the partition to directed paths on a directed graph is
> called "a partition to strokes on a directed graph". And all directed paths
> in the partition are called "strokes". C.1. Two different directed paths in
> a partition do not have the same edges. C.2. A union of two different paths
> in a partition does not become a directed path. In other word, a "stroke"
> is a locally maximal path on a directed graph.
>     Recently  I recomputed the terms of A131519 and I have found it is
> fault
>     The correct one is    1, 6, 58, 490, ....    So  I am going to rewrite
> it  but I must confirm   it    Could anyone confirm   it and compute more
> terms ?    If the definition is difficult then feel free to ask anything
> about it
>     Yasutoshi
> --
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list