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

%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