A147878 - OEIS

%I #21 Feb 23 2023 09:55:28

%S 1,2,5,11,23,46,86,156,273,463,766,1241,1969,3073,4723,7157,10711,

%T 15850,23206,33654,48373,68955,97544,137002,191125,264955,365127,

%U 500349,682018,924982,1248502,1677530,2244229,2989952,3967732,5245354,6909211

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

%H Vaclav Kotesovec, <a href="/A147878/b147878.txt">Table of n, a(n) for n = 1..10000</a>

%H O. J. Rodseth, J. A. Sellers and H. Tverberg, <a href="http://dx.doi.org/10.1016/j.ejc.2008.10.006">Enumeration of the Degree Sequences of Non-Separable Graphs and Connected Graphs</a>, European Journal of Combinatorics 30 (2009), 1301-1317.

%H Gus Wiseman, <a href="/A147878/a147878.png">Connected multigraphs realizing each of the a(5) = 23 connected multigraphical graphical partitions of 10.</a>

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

%F a(n) = A000041(2*n) - 2*A000070(n) + 2*A000041(n) + A000041(n-1). - _Vaclav Kotesovec_, Nov 05 2016

%F 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

%e From _Gus Wiseman_, Oct 26 2018: (Start)

%e The a(1) = 1 through a(5) = 23 connected multigraphical partitions:

%e   (11)  (22)   (33)    (44)     (55)

%e         (211)  (222)   (332)    (433)

%e                (321)   (422)    (442)

%e                (2211)  (431)    (532)

%e                (3111)  (2222)   (541)

%e                        (3221)   (3322)

%e                        (3311)   (3331)

%e                        (4211)   (4222)

%e                        (22211)  (4321)

%e                        (32111)  (4411)

%e                        (41111)  (5221)

%e                                 (5311)

%e                                 (22222)

%e                                 (32221)

%e                                 (33211)

%e                                 (42211)

%e                                 (43111)

%e                                 (52111)

%e                                 (222211)

%e                                 (322111)

%e                                 (331111)

%e                                 (421111)

%e                                 (511111)

%e (End)

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

%o (PARI) a(n) = numbpart(2*n) - numbpart(n-1) - 2*sum(j=0, n-2, numbpart(j)); \\ _Michel Marcus_, Nov 04 2016

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

%K nonn

%O 1,2

%A _James A. Sellers_, Nov 16 2008

%E Offset corrected by _Michel Marcus_, Nov 04 2016