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

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

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..10.

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

terms[p_] := CoefficientRules[p, x /@ Range@Max[{0}, Cases[p, x[t_] :> t, \[Infinity]]]];
cycleindSymm[n_] := cycleindSymm[n] = terms@CycleIndexPolynomial[SymmetricGroup[n], x /@ Range[n]];
cycleindEdge[0|1] = 1;
cycleindEdge[n_] := cycleindEdge[n] = terms@Sum[Last[t] With[{tt = First[t]}, With[{ind = Select[Range@n, tt[[#]] != 0 &]},
    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]}];
v[1, _] = v[_, 1] = 1;
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]}];
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 A246536 A183248

Adjacent sequences: A309113 A309114 A309115 * A309117 A309118 A309119

Keyword

nonn,more

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

Status

approved