a stroke sequence on star graphs
y.kohmoto
zbi74583 at boat.zero.ad.jp
Tue Jan 13 08:42:01 CET 2004
Hello, seqfans.
I posted a sequence which enumerates number of partitions into strokes
on star graph.
I think this definition is the best.
I calculated these numbers drawing stars on a paper. I am not sure if
A(6) is correct or not. Please verify it.
%I A000001
%S A000001 0, 1, 3, 4, 9, 14, 56
%N A000001 A(n) gives number of partition to strokes on a star
graph which has n edges.
Where all edges on a star graph have directions.
Two arrangements are not distinguished if one is a rotation or
reflection of the other.
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 don't have the
same edges.
C.2. A union of two different paths in a partition don't become a
directed path.
In other word, a "stroke" is a locally maximal path on a directed
graph.
%e A000001 n=3 , it is the same graph as "Y"
Let's name the center node "0" and the terminal nodes "1",
"2", "3".
Four partitions exist as follows :
{1->0->2, 0->3}
{1->0->2, 3->0}
{1->0, 2->0, 3->0}
{0->1, 0->2, 0->3}
So, A(3)=4
%C A000001 This idea has its origin in the strokes made when writing
Japanese Kanji
%K A000001 nonn
%O A000001 0, 2
%A A000001 Yasutoshi Kohmoto (zbi74583 at boat.zero.ad.jp)
PS
I like the following formula. But I feel this description is not so
standard.
C.1. all i, j p_i in P & p_j in P -> p_i cap p_j = null
C.2. all i, j p_i in P & p_j in P -> not (p_i cup p_j = a
directed path)
where p_i represents variable for path, P is an abbreviation
for a Partition to directed paths on a directed graph.
Edwin Clark wrote :
>
>Yasutoshi,
>
>I am still thinking about your definition for A002620. I see
>that the number of different orientations (tournaments) of K_n is
>given in:
>
> http://mathworld.wolfram.com/Tournament.html
>
>Where it is stated that:
>
>"The number a(n) of nonisomorphic tournaments on n = 2, 3, 4,
>... nodes are 1, 2, 4, 12, 56, 456, ... (Sloane's A000568)".
>
>Note that these terms become quite large, for example for n = 13
>there are 48542114686912 non-isomorphic tournaments---yet you have
>only 42 for maximal number of strokes in K_n.
>
A compairing some sequences :
maximal number of members of partition to strokes on K_n < number of
edges on K_n << number of tournament << number of partitions to strokes
on K_n
where K_n are oriented.
S < T means that almost all terms s_i < t_i
" << " means that "much more than"
>What program did you use to compute the numbers for A002620?
>
A di-path is an arrow like this :
a -> b
Let's give numbers "0" to a tail of the arrow and "1" to a head of the
arrow. .
Then vertices become to have some 0s and 1s.
example.1.
a 0011 , b 0001
two arrows go from vertex a and two arrows come to vertex a.
three arrows go from vertex b and one arrow come to vertex b.
Consider the "partition to strokes of K_n" using the vertices with 0s
and 1s.
We enumerate maximal number of members of a partition.
n vertices with 0s and 1s maximal number of members or strokes
2 0 , 1 1
3 00, 01, 11 1+1=2
To make a partition on K_3 :
We must add a vertex with 00, because if it has 01 then two arrows who
comes and goes are able to be parts of one stroke, this partition never
gives the maximal number of members.
Where it is possible to add a vertex with 11, because 0s and 1s are
symmetric.
So, two arrows go to two vertices 0 and 1 on K_2. They become 01 and 11
on K_3.
A couple of 0 and 1 means that a couple of arrows are parts of one
stroke, so the number of members of the partition never increases.
So, if we count the number of vertices whose 0s <= 1s on K_n-1, then
this number becomes the difference of maximal number of members of partition
on K_n-1 and on K_n.
See the case n=2, the vertex 1 satisfies 0s <= 1s, so maximal number of
members = 1+1=2.
We are able to count in the same way the cases 4, 5, 6, ....
4 000, 001, 011, 111 2+2=4
5 0000, 0001, 0011, 0111, 1111 4+2=6
6 00000, 00001, 00011, 00111, 01111, 11111 6+3=9
7 000000, 000001, 000011, 000111, 001111, 011111, 111111
9+3=12
>Is A002620(n) = also the number of partitions of a tournament on n
>vertices into strokes?
>
No, it is smaller than the number of partitions of a tournament on n
vertices into strokes
>Why not define a stroke to be a maximal directed path in a digraph? This
>means a directed path which cannot be extended. I don't see why you add
>the word "local" to the definition of stroke. What precisely is the
>definition of a "local maximal di-path"?
>
See the partition on triangle di-graph {0->1, 0->2->1}.
0->1 is locally maximal, because it is not a part of the other
di-path. But it is not maximal, because 0->2->1 is maximal.
I suppose you might correct because you are a native speaker of English.
Then how do you call the di-path 0->2-.1?
>Also when you count the "possible maximal number of strokes on K_n" do you
>allow the maximal strokes to overlap?
>
No. See the condition 1.
>--Edwin
>
>
>PS If you want to discuss this further in a public forum it might be a
>good idea to raise the question on GRAPHNET which is a mailing list for
>the discussion of graph theoretic questions. There seems to be no interest
>in discussing this question on seqfan. You can subscribe to GRAPHNET at
>
>http://listserv.nodak.edu/archives/graphnet.html
>
>However, the first thing that graph theorists will want is clear and
>precise definitions of all terms involved.
>
Thanks for your good advices.
>
>
>-----------------------------------------------------------------
>
>
>On Sat, 27 Dec 2003, y.kohmoto wrote:
>
>> Hello, seqfans
>> I posted two sequences to OEIS.
>>
>> %I A002620
>> %S A002620 0, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, ....
>>
>> %N A002620 A(n) gives possible maximal numbers of strokes on K_n.
>> Where all edges on K_n have directions.
>> A "stroke" is defined as follows :
>> A local maximal di-path on di- graph.
>>
>> %e A002620
>> n=3 , maximal two strokes exist, "x -> y -> z" and " x -> z" , so
>> A(3)=2 .
>> n=4, maximal four strokes exist, "u -> x -> z" and "u -> y" and "u ->
z"
>> and "x -> y -> z" , so A(4)=4 .
>> %Y A002620 Cf.A000001
>> %K A002620 nonn
>> %O A002620 1,3
>> %A A002620 Yasutoshi Kohmoto (zbi74583 at boat.zero.ad.jp)
>>
>> I asked Neil to add some of this description on comment line of
>> a002620.
>>
>> %I A000001
>> %S A000001 0, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, ....
>> %N A000001 B(n) gives minimal numbers of strokes on K_n.
>> Where all edges on K_n have directions.
>> A "stroke" is defined as follows :
>> A local maximal di-path on di- graph.
>> %C A000001 If B(n)=1 then K_n has an Euler path.
>> %Y A000001 Cf. A002620
>> %K A000001 nonn
>> %O A000001 1,4
>> %A A000001 Yasutoshi Kohmoto (zbi74583 at boat.zero.ad.jp)
>>
>>
>> This definition of "stroke" has still some ambiguousness.
>> At least, a condition that different two strokes don't have the same
>> edges is needed.
>> Even if the condition is satisfied, there are some ambiguousness.
>> For example : a di-graph "H"
>> a->b->c->d,
>> x->b, c->y
>> Four sets of strokes are able to exist.
>> {a->b->c->d, x->b, c->y}
>> {a->b->c->y, x->b, c->d}
>> {x->b->c->d, a->b, c->y}
>> {x->b->c->y, a->b, c->d}
>> But, after all, the number of strokes is the same.
>> So, the number doesn't depend on these sets.
>>
>> Do you understand what I am considering about?
>>
>> Yasutoshi
>>
>>
>
>------------------------------------------------------------
> W. Edwin Clark, Math Dept, University of South Florida,
> http://www.math.usf.edu/~eclark/
>------------------------------------------------------------
>
>
>
>
>
More information about the SeqFan
mailing list