cp's OEIS Frontend

A309116 a(n) = number of cographs on n points.

%I A309116 #32 Feb 27 2025 08:25:38
%S A309116 1,3,25,1299,1974452,94345468975,152799292695935115,
%T A309116 10526127565809458484649781,38375912431199015810067477044326371,
%U A309116 9002076475560099357419498216602893054297145089,162015966626938926212463690033352243299416773774432388589099
%N A309116 a(n) = number of cographs on n points.
%C A309116 Here, a cograph is basically a partition of unlabeled edges of the complete graph on n unlabeled vertices. - _Andrey Zabolotskiy_, Aug 27 2022
%H A309116 Robert Haas, <a href="https://arxiv.org/abs/1905.12627">Cographs</a>, arXiv:1905.12627 [math.GM], 2019, p. 3, 57.
%H A309116 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 A309116 Marko Riedel, <a href="/A309116/a309116.maple.txt">Colorings of the complete graph Kn with any number of swappable colors</a>.
%t A309116 cycleIndSymm[n_] := cycleIndSymm[n] = CoefficientRules[CycleIndexPolynomial[ SymmetricGroup[n], x /@ Range[n]], x /@ Range[n]];
%t A309116 cycleIndEdge[n_] := cycleIndEdge[n] = CoefficientRules[Sum[Last[t] With[{tt = First[t]}, With[{ind = Flatten@Position[tt, Except[0], Heads -> False]}, Product[x[LCM@@p]^(GCD@@p Times@@tt[[p]]), {p, Subsets[ind, {2}]}] 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, cycleIndSymm[n]}], x /@ Range[n (n-1)/2]];
%t A309116 v[n_, m_] := With[{dv = Divisors /@ Range[m]}, Sum[Last[a] With[{ra = Flatten@Position[First@a, Except[0], Heads -> False]}, Sum[Last[b] Product[(dv[[va]].b[[1, dv[[va]]]])^a[[1, va]], {va, ra}], {b, cycleIndSymm[m]}]], {a, cycleIndEdge[n]}]];
%t A309116 a[2] = 1; a[3] = 3;
%t A309116 a[n_] := 1 + v[n, -1 + n (n-1)/2];
%t A309116 Table[a[n], {n, 2, 7}] (* _Andrey Zabolotskiy_, Feb 06 2024, after _Marko Riedel_ *)
%Y A309116 Cf. partitions into no more than 2..5 parts: A007869, A230367, A233748, A233894.
%K A309116 nonn
%O A309116 2,2
%A A309116 _Michael De Vlieger_, Jul 13 2019
%E A309116 a(6)-a(9) from _Andrey Zabolotskiy_, Aug 27 2022
%E A309116 a(10) from _Andrey Zabolotskiy_, Feb 06 2024
%E A309116 a(11)-a(12) from _Andrey Zabolotskiy_, Feb 26 2025