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

Christian Sievers seqfan at duvers.de
Wed May 3 15:19:43 CEST 2023

```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
```