[seqfan] Re: Partition into Stroke of the star graph

[Christian Sievers]

Some remarks and results:

1) The value of A089243(1)=2 can be disputed.

We can only distinguish the two stroke sets for a star graph with one
edge if the center node is distinguished. In all other cases (even n=0)
it is obvious which point is the center. 

2) In the mail, what does this mean?

>     1, 2, 3, 4, 9, 22, 61, 200,    Off SET 0    0 means Phi
                                                  ^^^^^^^^^^^ 
It's not from the OEIS entry.

3) Also from the mail:

>     The definition is for the case of directed , labelled , mirror
> symmetric exist    I computed  all cases  that exist eight

We can certainly consider variations of the series, like undirected
strokes (then we act on sets of sets of size 2, instead of sets of
pairs, and count each 2-stroke possibility only once)
and/or only consider stroke sets equivalent if one can be obtained from
the other by a rotation and not allow reflections (so replace the
dihedral group by a cyclic group),
but I don't see what labeled vs unlabeled should mean.
Without labels I can't differentiate the nodes, and then the symmetries
become meaningless.

I computed the cases that make sense to me, here are the results
(code at the end of the mail):

  # as before
  gap> List([1..10],i->f(i,true,true));
  [ 2, 3, 4, 9, 22, 61, 200, 689, 3054, 12110 ]

  # only rotations are equivalent
  gap> List([1..10],i->f(i,true,false));
  [ 2, 3, 6, 12, 34, 98, 374, 1290, 5962, 23768 ]

  # undirected
  gap> List([1..10],i->f(i,false,true));
  [ 1, 2, 2, 5, 6, 17, 27, 83, 185, 608 ]
  
  # undirected and only rotations
  gap> List([1..10],i->f(i,false,false));
  [ 1, 2, 2, 5, 6, 18, 34, 108, 294, 984 ]

One might argue that in the undirected case the maximal stroke condition
allows at most one 1-stroke. Then the results (code not given here) are
  [ 1, 1, 1, 2, 3, 5, 11, 17, 65, 79 ]
with reflection and rotations and
  [ 1, 1, 1, 2, 3, 5, 15, 18, 105, 105 ]
with only rotations considered equivalent.

Of these, only the original series is in the OEIS.


Best
Christian
-- 

f := function(n,dir,refl)
  local s, g, mult, act, h, res;

  if dir then
    mult := 2;
    act := OnSetsTuples;
  else
    mult := 1;
    act := OnSetsSets;
  fi;

  s := SymmetricGroup( n );

  if refl then
    g := DihedralGroup( IsPermGroup, 2*n);
  else
    g := CyclicGroup( IsPermGroup, n);
  fi;

  h := function( l )
    local tss,x;
    tss := Set([1..l], i->[2*i-1, 2*i]); # a set of l two-strokes
    x := Orbit( s, tss, act ); # all such sets
    return Size( OrbitsDomain( g, x, act ) );
  end;
        
  res := mult * Sum( [0..QuoInt(n-1,2)], h );
  if IsEvenInt(n) then
    res := res + h( n/2 );
  fi;
  return res;
end;