[seqfan] Re: Partition Into Stroke of Star graph

[Christian Sievers]

Dear Yasutoshi,

>     Partition of graph G=(V,E) into strokes is a collection of directed
> edge-disjoint trails (viewed as sets of directed edges) in G such that (0)
> E must be undirected (i) no two trails can be concatenated into a single
> one; (ii) the corresponding undirected edges form a partition of E.
> One more condition (0) is added

I don't see the point of this. Is it meant as a clarification?

>     First of  all, does my definition have  any sense ?
>     Did you computed the case of directed, labelled, mirror symmetric ?
>     Mine is the following
> 
>            1, 2, 4, 8, 50,   ....    OFF SET 0    0 mean  phi
                                                    ^^^^^^^^^^^
This still doesn't make any sense to me.

>     Could you compute it  and explain the case of n=3 with a figure like
> this ?
> 
>            1
>            0
>       2         3
> 
>            For n = 3
>             103+02, 103+20, 301+02, 301+20, 203+01, 203+10,
>            03+02+01, 30+20+10;

I didn't understand the details in your earlier mail, but you mentioned
A089243, which says "up to rotations and reflections around the center
node", so that is what I have computed.
For n=3, this gives 4 ways. If you have a stroke a-0-b of length 2,
rotations and reflections can bring it into position 1-0-2. This
combines with 2 directions for the remaining stroke. And we have 2
options where all strokes are of length 1.
So we have these options: 102+03, 102+30, 01+02+03, 10+20+30.

>From your example I guess you want to allow only one reflection, with
reflection axis going through 0 and 1.
You'd have to specify what you want for even n: the reflection axis
could go through the center point and (a) two other nodes,
or (b) no other node, like this for n=4:

(a) .                   (b) .
    .                       .
    .                       .
    1                     4 . 1
    |                      \./
  4-0-2                     0
    |                      /.\
    3                     3 . 2
    .                       .
    .                       .
    .                       .

 fixes 1 and 3           fixes no node
 exchanges 2<->4         exchanges 1<->4, 2<->3

For n=4, I get the same result in both cases: 22, but that is no longer
the case for bigger n.
(Your number 50 is very strange: for n=4, there are only 38 stroke sets
in total, without considering any of them equivalent.)

With my helper function from an earlier mail
(it's PARI code, but almost readable as math)

  p(n,t,o)=o*sum(k=0,(n-1)/2,n!/(k!*(n-2*k)!)*t^k)+if(n%2==0,n!/(n/2)!*t^(n/2))

the numbers can be computed like this:

if n is odd: f(n)=(p(n,1,2)+2*p((n-1)/2,2,1))/2
if n is even,
  case a:    a(n)=(p(n,1,2)+2*p(n/2-1,2,2)+2*p(n/2-1,2,1))/2
  case b:    b(n)=(p(n,1,2)+p(n/2,2,2))/2

So here are the first numbers:

 n     1    2    3    4    5    6    7      8      9      10

 f     2         8         86       1316         26858
 a          4        22        282        5136          118702
 b          3        22        284        5146          118812


Hope this helps,
Christian