A340026 Number of connected graphs with n integer labeled vertices covering an initial interval of positive integers.

1, 1, 2, 12, 151, 3845, 192215, 18642053, 3534415032, 1322914720382, 983866402492022, 1458669558830420947, 4317992152324160500565, 25541957673530923214876165, 302031658361424323818453728818, 7141206379474081326199747144178588, 337646560987347470614138636684815527025

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

Example

a(2) = 2 because there is 1 connected graph on 2 vertices which can either have both vertices labeled 1 or one vertex labeled 1 and the other 2.
a(3) = 12 because there are 2 connected graphs on 3 vertices. The complete graph K_3 can be labeled in 4 ways (111, 112, 122, 123) and the path graph P_3 can be labeled in 8 ways (111, 112, 121, 122, 212, 123, 132, 213).

Prog

(PARI) \\ See A340023 for G(n, k).
InvEulerT(v)={my(p=log(1+x*Ser(v))); dirdiv(vector(#v, n, polcoef(p, n)), vector(#v, n, 1/n))}
seq(n)={my(v=concat([1], InvEulerT(vector(n, n, G(n, y))))); sum(k=0, n, subst(v, y, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)))}

Crossrefs

Cf. A340023, A340025, A340027.

Sequence in context: A289987 A105558 A322399 * A279011 A279183 A126777

Adjacent sequences: A340023 A340024 A340025 * A340027 A340028 A340029

Keyword

nonn

Author

Andrew Howroyd, Jan 02 2021

Status

approved