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

1, 3, 25, 1299, 1974452, 94345468975, 152799292695935115, 10526127565809458484649781, 38375912431199015810067477044326371, 9002076475560099357419498216602893054297145089, 162015966626938926212463690033352243299416773774432388589099

Offset

2,2

Comments

Here, a cograph is basically a partition of unlabeled edges of the complete graph on n unlabeled vertices. - Andrey Zabolotskiy, Aug 27 2022

Links

Table of n, a(n) for n=2..12.

Robert Haas, Cographs, arXiv:1905.12627 [math.GM], 2019, p. 3, 57.

Robert Haas, Intersection Cographs and Aesthetics, Journal of Humanistic Mathematics, 12 (2022), 4-23.

Marko Riedel, Colorings of the complete graph Kn with any number of swappable colors.

Mathematica

cycleIndSymm[n_] := cycleIndSymm[n] = CoefficientRules[CycleIndexPolynomial[ SymmetricGroup[n], x /@ Range[n]], x /@ Range[n]];
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]];
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]}]];
a[2] = 1; a[3] = 3;
a[n_] := 1 + v[n, -1 + n (n-1)/2];
Table[a[n], {n, 2, 7}] (* Andrey Zabolotskiy, Feb 06 2024, after Marko Riedel *)

Crossrefs

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

Sequence in context: A012764 A219275 A101733 * A094815 A393762 A246536

Adjacent sequences: A309113 A309114 A309115 * A309117 A309118 A309119

Keyword

nonn

Author

Michael De Vlieger, Jul 13 2019

Extensions

a(6)-a(9) from Andrey Zabolotskiy, Aug 27 2022

a(10) from Andrey Zabolotskiy, Feb 06 2024

a(11)-a(12) from Andrey Zabolotskiy, Feb 26 2025

Status

approved