login
a(n) = number of cographs on n points.
1

%I #27 Feb 06 2024 10:34:24

%S 1,3,25,1299,1974452,94345468975,152799292695935115,

%T 10526127565809458484649781,38375912431199015810067477044326371

%N a(n) = number of cographs on n points.

%C Here, a cograph is basically a partition of unlabeled edges of the complete graph on n unlabeled vertices. - _Andrey Zabolotskiy_, Aug 27 2022

%H Robert Haas, <a href="https://arxiv.org/abs/1905.12627">Cographs</a>, arXiv:1905.12627 [math.GM], 2019, p. 3, 57.

%H Robert Haas, <a href="https://doi.org/10.5642/jhummath.202201.03">Intersection Cographs and Aesthetics</a>, Journal of Humanistic Mathematics, 12 (2022), 4-23.

%H Marko Riedel, <a href="/A309116/a309116.maple.txt">Colorings of the complete graph Kn with any number of swappable colors</a>.

%t terms[p_] := CoefficientRules[p, x /@ Range@Max[{0}, Cases[p, x[t_] :> t, \[Infinity]]]];

%t cycleindSymm[n_] := cycleindSymm[n] = terms@CycleIndexPolynomial[SymmetricGroup[n], x /@ Range[n]];

%t cycleindEdge[0|1] = 1;

%t cycleindEdge[n_] := cycleindEdge[n] = terms@Sum[Last[t] With[{tt = First[t]}, With[{ind = Select[Range@n, tt[[#]] != 0 &]},

%t Product[x[LCM@@p]^(GCD@@p Times@@tt[[p]]), {p, Subsets[ind, {2}]}]

%t Product[With[{e = tt[[k]]}, x[k]^(k e (e-1)/2 + Quotient[k-1, 2] e) If[EvenQ[k], x[k/2]^e, 1]], {k, ind}]

%t ]], {t, cycleindSymm[n]}];

%t v[1, _] = v[_, 1] = 1;

%t v[n_, m_] := Sum[Last[a] Last[b] With[{aa = First@a, bb = First@b}, Product[Sum[vb bb[[vb]], {vb, Intersection[Divisors[va], Range@m]}]^aa[[va]], {va, Select[Range@Length@aa, aa[[#]] != 0 &]}]], {b, cycleindSymm[m]}, {a, cycleindEdge[n]}];

%t a[n_] := 1 + v[n, -1 + n (n-1)/2];

%t Table[a[n], {n, 2, 7}] (* _Andrey Zabolotskiy_, Feb 06 2024, after _Marko Riedel_ *)

%Y Cf. partitions into no more than 2..5 parts: A007869, A230367, A233748, A233894.

%K nonn,more

%O 2,2

%A _Michael De Vlieger_, Jul 13 2019

%E a(6)-a(9) from _Andrey Zabolotskiy_, Aug 27 2022

%E a(10) from _Andrey Zabolotskiy_, Feb 06 2024