login
A265582
Number of (unlabeled) connected loopless multigraphs such that the sum of the numbers of vertices and edges is n.
2
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
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
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
KEYWORD
nonn
AUTHOR
Michael Joseph, Dec 10 2015
EXTENSIONS
Terms a(19) and beyond from Andrew Howroyd, Feb 01 2020
STATUS
approved