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
Keywords
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
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) ~ 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