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

[Christian Sievers]

On Wed, May 03, 2023 at 03:26:21PM +0900, Yasu Koh wrote:

>     I recomputed A089243       ,  and I think it is incorrect
> 
>     1, 2, 3, 4, 9, 22, 61, 200,    Off SET 0    0 means Phi

I get the same numbers.

>     The definition is the following    I think it is the best that Max
> Aleksayev gave
> 
>     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 (i)
> no two trails can be concatenated into a single one; (ii) the corresponding
> undirected edges form a partition of E.

There are strokes of length one and two. If we know all the two-strokes
of a stroke set, there are only two possibilities for the remaining
one-strokes (if there are any): they must all be directed to or away
from the central point. So we have to count the inequivalent disjoint
subsets of two-strokes and count those twice that don't cover the graph.

Here is some naive GAP code to do this for n>=1:

----------------------------------------
h:=function(n,l)
# compute the number of inequivalent ways to select
# a set of l two-strokes in a star graph with n edges
  local tss,x;
  tss := Set( [1..l], i -> [ 2*i-1, 2*i ] ); # a set of l two-strokes
  x := Orbit( SymmetricGroup(n), tss, OnSetsTuples ); # all such sets
  return Size( OrbitsDomain( DihedralGroup( IsPermGroup, 2*n ), x,
                             OnSetsTuples ) );
end;

f := function(n)
  local res;
  res := 2 * Sum( [0..QuoInt(n-1,2)], i -> h(n,i) );
  if IsEvenInt(n) then
    res := res + h( n, n/2 );
  fi;
  return res;
end;
----------------------------------------

This gives

  gap> List([1..10],f);
  [ 2, 3, 4, 9, 22, 61, 200, 689, 3054, 12110 ]

Using Burnside's lemma should give a more efficient way to compute this
and maybe even a nice formula.

The number of partitions of a star graph with an even number of edges
into only two-strokes seems to be given by A260847.

  gap> List([1..5],i->h(2*i,i));
  [ 1, 3, 13, 121, 1538 ]


All the best
Christian