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

Max Alekseyev maxale at gmail.com
Sat May 13 14:41:27 CEST 2023

```Hi Christian,

Nice approach!

Regards,
Max

On Tue, May 9, 2023 at 11:10 PM Christian Sievers <seqfan at duvers.de> wrote:

> Hi,
>
> can compute the first 1000 values in very few seconds:
>
> ----------------------------------------
>
> 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))
>
> f(n)=(sumdiv(n,d,eulerphi(d)*p(n/d,d,2))+if(n%2,2*n*p((n-1)/2,2,1),n/2*p(n/2,2,2)+n*p(n/2-1,2,2)+n*p(n/2-1,2,1)))/(2*n)
> ----------------------------------------
>
> p counts the number of ways to choose any number of disjoint ordered
> pairs from n elements, giving each pair one of t colors, and then select
> one more color out of o if there are any remaining elements.
> (This has the exponential generating function exp(t*x^2)*(o*exp(x)-o+1).)
>
> It allows to compute the number of fixed points of stroke sets under the
> action of the dihedral group and so to get the number of inequivalent
> ones using Burnside's lemma.
> For the variant where only roations are considered equivalent, use just
> the sumdiv term divided by n.
>
> Here are the first 50 values:
>
> ? for(n=1,50,print(n," ",f(n)))
> 1 2
> 2 3
> 3 4
> 4 9
> 5 22
> 6 61
> 7 200
> 8 689
> 9 3054
> 10 12110
> 11 61132
> 12 274264
> 13 1515134
> 14 7498195
> 15 44301928
> 16 238206692
> 17 1490114770
> 18 8605537805
> 19 56612534420
> 20 348083793872
> 21 2396294898646
> 22 15577794980189
> 23 111781094032984
> 24 763986810923430
> 25 5695585712379834
> 26 40737451407877858
> 27 314659903304460936
> 28 2346114228216173844
> 29 18731228250847294030
> 30 145109837316965437826
> 31 1195066253760346423712
> 32 9592229725346440656742
> 33 81340937512735027807354
> 34 674795297567241780477740
> 35 5882489174060397510578908
> 36 50330553591560376090682324
> 37 450400644641325186620852150
> 38 3966984700515558196029776497
> 39 36395431293150302939930313328
> 40 329439111819009467734966851402
> 41 3095097406238573860130595898762
> 42 28749030486241115625027480791678
> 43 276295925545953616240700587608044
> 44 2630050520790428420279989319082272
> 45 25831300212531909407012114984617330
> 46 251682795041174604804507762367483643
> 47 2523945039282347194822559750439162160
> 48 25143787970923110454345997069847180668
> 49 257243792386300265157341879932495071806
> 50 2617626488843020489832788087533723522594
>
>
> BTW, among the variations considered in my last mail were these:
>
> > 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.
>
> I've noticed that, while they are not in the OEIS, they are alternations
> of A132101 and A054499 (without the first term) resp.
> A001147 and A007769 (also without the first term).
>
>
> All the best
> Christian
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
```