cp's OEIS Frontend

A058862 Number of chordal labeled graphs (connected or not) with n nodes.

%I A058862 #32 Jun 13 2025 16:08:59
%S A058862 1,2,8,61,822,18154,617675,30888596,2192816760,215488096587,
%T A058862 28791414081916,5165908492061926,1234777416771739141,
%U A058862 391374602835914994534,164188178238479142509452
%N A058862 Number of chordal labeled graphs (connected or not) with n nodes.
%D A058862 N. C. Wormald, Counting labeled chordal graphs. Graphs Combin. 1 (1985), no. 2, 193-200.
%H A058862 Ursula Hebert-Johnson, Daniel Lokshtanov, and Eric Vigoda, <a href="https://arxiv.org/abs/2308.09703">Counting and Sampling Labeled Chordal Graphs in Polynomial Time</a>, arXiv:2308.09703 [cs.DS], 2023.
%H A058862 Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka, <a href="https://arxiv.org/abs/1804.03822">Enumerating All Subgraphs without Forbidden Induced Subgraphs via Multivalued Decision Diagrams</a>, arXiv:1804.03822 [cs.DS], 2018.
%F A058862 From the relation G(x)=exp(g(x)) between generating functions for connected g(x) and all G(x) labeled structures and considering generating functions for chordal graphs (c_n, A007134), we have a(n) = c(n) + 1/n * Sum_{k=1}^(n - 1) k * binomial(n, k) * c(k) * a(n - k). [Formula edited by _Michael De Vlieger_, Jul 04 2018]
%t A058862 A007134 = Cases[Import["https://oeis.org/A007134/b007134.txt", "Table"],
%t A058862    {_, _}][[All, 2]];
%t A058862 c[n_ /; 1 <= n <= Length[A007134]] := A007134[[n]];
%t A058862 a[n_] := a[n] = If[n == 0, 0, c[n] + 1/n * Sum[k*Binomial[n, k]*c[k]*
%t A058862    a[n - k], {k, 1, n + 1}]];
%t A058862 Table[a[n], {n, 1, 15}] (* _Jean-François Alcover_, Jul 20 2022 *)
%Y A058862 Cf. A007134.
%K A058862 nonn,nice,more
%O A058862 1,2
%A A058862 _Robert Castelo_, Jan 06 2001
%E A058862 a(13) from formula by _Falk Hüffner_, Jul 24 2019
%E A058862 a(14)-a(15) from _Brendan McKay_, Jun 05 2021