「自由クラス理論」非標準集合論コミュのThe archive of mails No.6

> ----- Original Message -----
>
> From: "Max Alekseyev" <maxale@gmail.com>
> To: "Sequence Fanatics Discussion list" <seqfan@list.seqfan.eu>
> Date: 2022/02/05 土 06:01
> Subject: [seqfan] Re: Partition into Stroke
>
>
> 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.
>
> Regards,
> Max
>
> ---------- Forwarded message ---------
> From: Max Alekseyev <maxale@gmail.com>
> Date: Sun, Sep 9, 2007 at 11:37 PM
> Subject: Re: RE : partition into strokes
> To: koh <zbi74583@boat.zero.ad.jp>
> Cc: <seqfan@ext.jussieu.fr>
>
>
> On 9/7/07, koh <zbi74583@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 =
> v_iv_{i+1}
> >>> 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
> formula:
>
> 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,
> y=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
> n>4.
>
> Regards,
> Max
>
> On Fri, Jan 21, 2022 at 2:12 AM <zbi74583_boat@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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>