A265582 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A265582

Number of (unlabeled) connected loopless multigraphs such that the sum of the numbers of vertices and edges is n.

1, 1, 0, 1, 1, 2, 3, 6, 10, 21, 41, 87, 187, 423, 971, 2324, 5668, 14224, 36506, 95880, 257081, 703616, 1962887, 5578529, 16137942, 47492141, 142093854, 432001458, 1333937382, 4181500703, 13301265585, 42918900353, 140423545125, 465712099790, 1565092655597

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

Also the number of connected skeletal 2-cliquish graphs with n vertices. See Einstein et al. link below.

a(n) can be computed from A265580 and/or A265581, and partitions of n, by taking all loopless multigraphs (V,E) with |V| + |E| = n and subtracting out the disconnected ones.

a(n) <= A265580(n) except when n=1, and a(n) < A265580(n) for n>=6.

LINKS

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

D. Einstein, M. Farber, E. Gunawan, M. Joseph, M. Macauley, J. Propp and S. Rubinstein-Salzedo, Noncrossing partitions, toggles, and homomesies, arXiv:1510.06362 [math.CO], 2015.

FORMULA

From Andrew Howroyd, Feb 01 2020: (Start)

a(n) = Sum_{k=1..ceiling(n/2)} A191646(n-k, k) for n > 0.

Inverse Euler transform of A265581. (End)

EXAMPLE

For n = 5, the a(5) = 2 such multigraphs are the graph with three vertices and edges from one vertex to each of the other two, and the graph with two vertices connected by three edges.

PROG

(PARI) \\ See A191646 for G, InvEulerMT.

seq(n)={my(v=InvEulerMT(vector((n+1)\2, k, 1 + y*Ser(G(k, n-1), y)))); Vec(1 + sum(i=1, #v, v[i]*y^i) + O(y*y^n))} \\ Andrew Howroyd, Feb 01 2020

CROSSREFS

Cf. A191646, A265580, A265581.

Sequence in context: A002988 A138347 A211180 * A242563 A240513 A036650

Adjacent sequences: A265579 A265580 A265581 * A265583 A265584 A265585

KEYWORD

nonn

AUTHOR

Michael Joseph, Dec 10 2015

EXTENSIONS

Terms a(19) and beyond from Andrew Howroyd, Feb 01 2020

STATUS

approved