|
|
A058862
|
|
Number of chordal labeled graphs (connected or not) with n nodes.
|
|
4
|
|
|
1, 2, 8, 61, 822, 18154, 617675, 30888596, 2192816760, 215488096587, 28791414081916, 5165908492061926, 1234777416771739141, 391374602835914994534, 164188178238479142509452
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
REFERENCES
|
N. C. Wormald, Counting labeled chordal graphs. Graphs Combin. 1 (1985), no. 2, 193-200.
|
|
LINKS
|
|
|
FORMULA
|
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]
|
|
MATHEMATICA
|
A007134 = Cases[Import["https://oeis.org/A007134/b007134.txt", "Table"],
{_, _}][[All, 2]];
a[n_] := a[n] = If[n == 0, 0, c[n] + 1/n * Sum[k*Binomial[n, k]*c[k]*
a[n - k], {k, 1, n + 1}]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,more
|
|
AUTHOR
|
Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|