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

[Christian Sievers]

Hi,

I couldn't stop thinking about this, so here is some PARI code that
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