A147878 The number of degree sequences with degree sum 2n representable by a connected graph (with multiple edges allowed).

1, 2, 5, 11, 23, 46, 86, 156, 273, 463, 766, 1241, 1969, 3073, 4723, 7157, 10711, 15850, 23206, 33654, 48373, 68955, 97544, 137002, 191125, 264955, 365127, 500349, 682018, 924982, 1248502, 1677530, 2244229, 2989952, 3967732, 5245354, 6909211

Offset: 1

Author

James Sellers, Nov 16 2008

Keywords

• nonn

Examples

			From _Gus Wiseman_, Oct 26 2018: (Start)
The a(1) = 1 through a(5) = 23 connected multigraphical partitions:
  (11)  (22)   (33)    (44)     (55)
        (211)  (222)   (332)    (433)
               (321)   (422)    (442)
               (2211)  (431)    (532)
               (3111)  (2222)   (541)
                       (3221)   (3322)
                       (3311)   (3331)
                       (4211)   (4222)
                       (22211)  (4321)
                       (32111)  (4411)
                       (41111)  (5221)
                                (5311)
                                (22222)
                                (32221)
                                (33211)
                                (42211)
                                (43111)
                                (52111)
                                (222211)
                                (322111)
                                (331111)
                                (421111)
                                (511111)
(End)
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..10000
• O. J. Rodseth, J. A. Sellers and H. Tverberg, Enumeration of the Degree Sequences of Non-Separable Graphs and Connected Graphs, European Journal of Combinatorics 30 (2009), 1301-1317.
• Gus Wiseman, Connected multigraphs realizing each of the a(5) = 23 connected multigraphical graphical partitions of 10.

Crossrefs

Cf. A000070, A000569, A007717, A096373, A147877, A209816, A320911, A320921 (no multiedges), A320923.

Programs

Maple

with(combinat): seq(numbpart(2*m) - numbpart(m - 1) - 2*add(numbpart(j), j = 0 .. m-2), m=1..60);

PARI

a(n) = numbpart(2*n) - numbpart(n-1) - 2*sum(j=0, n-2, numbpart(j)); \\ Michel Marcus, Nov 04 2016

Formula

a(n) = p(2n) - p(n-1) - 2*Sum_{j=0..n-2} p(j).

a(n) = A000041(2*n) - 2*A000070(n) + 2*A000041(n) + A000041(n-1). - Vaclav Kotesovec, Nov 05 2016

a(n) ~ exp(2*Pi*sqrt(n/3))/(8*sqrt(3)*n) * (1 - (sqrt(3)/(2*Pi) + Pi/(48*sqrt(3))) /sqrt(n)). - Vaclav Kotesovec, Nov 05 2016

Extensions

Offset corrected by Michel Marcus, Nov 04 2016