login
Number of graphical partitions of 2n.
79

%I #76 Jul 14 2022 09:36:10

%S 1,2,5,9,17,31,54,90,151,244,387,607,933,1420,2136,3173,4657,6799,

%T 9803,14048,19956,28179,39467,54996,76104,104802,143481,195485,264941,

%U 357635,480408,642723,856398,1136715,1503172,1980785

%N Number of graphical partitions of 2n.

%C A partition of n is a sequence p_1, ..., p_k for some k with p_1 >= p_2 >= ... >= p_k and p_1+...+p_k=n. A partition is graphical if it is the degree sequence of a simple graph (this requires that n be even). Some authors set a(0)=1 by convention.

%H T. D. Noe, <a href="/A000569/b000569.txt">Table of n, a(n) for n = 1..860</a>. [Terms 1 through 110 were computed by Tiffany M. Barnes and Carla D. Savage; terms 111 through 585 were computed by Axel Kohnert; terms 586 to 860 by Wang Kai, Jun 05 2016; a typo of a(547) in <a href="http://www.mathe2.uni-bayreuth.de/axel/numberofgraphicalpartitions.pdf">Number of Graphical Partitions</a> is corrected by Wang Kai, Aug 03 2016]

%H Tiffany M. Barnes and Carla D. Savage, <a href="http://dx.doi.org/10.1016/S0166-218X(97)00022-X">Efficient generation of graphical partitions</a> Discrete Appl. Math. 78 (1997), no. 1-3, 17-26.

%H T. M. Barnes and C. D. Savage, <a href="https://doi.org/10.37236/1205">A recurrence for counting graphical partitions</a>, Electronic J. Combinatorics, 2 (1995).

%H K. Blum, <a href="https://arxiv.org/abs/2103.03196">Bounds on the Number of Graphical Partitions</a>, arXiv:2103.03196 [math.CO], 2021. See Table on p. 7.

%H P. Erdõs and T. Gallai, <a href="https://users.renyi.hu/~p_erdos/1961-05.pdf">Graphs with a given degree of vertices</a>, Mat. Lapok, 11 (1960), 264-274.

%H P. Erdős and L. B. Richmond, <a href="https://doi.org/10.1007/BF01202789">On graphical partitions</a> Combinatorica 13 (1993), no. 1, 57-63.

%H Axel Kohnert, <a href="https://doi.org/10.37236/1845">Dominance Order and Graphical Partitions</a>, Electronic J. Combinatorics, 11 (2004).

%H Gerard Sierksma and Han Hoogeveen, <a href="http://dx.doi.org/10.1002/jgt.3190150209">Seven criteria for integer sequences being graphic</a>, J. Graph Theory 15 (1991), no. 2, 223-231.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphicalPartition.html">Graphical partition.</a>

%H Gus Wiseman, <a href="/A000569/a000569.png">Simple graphs realizing each of the a(6) = 31 graphical partitions of 12.</a>

%H <a href="/index/Gra#graph_part">Index entries for sequences related to graphical partitions</a>

%e a(2)=2: the graphical partitions of 4 are 2+1+1 and 1+1+1+1, corresponding to the degree sequences of the graphs V and ||.

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

%e The a(1) = 1 through a(5) = 17 graphical partitions:

%e (11) (211) (222) (2222) (3322)

%e (1111) (2211) (3221) (22222)

%e (3111) (22211) (32221)

%e (21111) (32111) (33211)

%e (111111) (41111) (42211)

%e (221111) (222211)

%e (311111) (322111)

%e (2111111) (331111)

%e (11111111) (421111)

%e (511111)

%e (2221111)

%e (3211111)

%e (4111111)

%e (22111111)

%e (31111111)

%e (211111111)

%e (1111111111)

%e (End)

%t << MathWorld`Graphs`

%t Table[Count[RealizeDegreeSequence /@ Partitions[n], _Graph], {n, 2, 20, 2}]

%t (* second program *)

%t prptns[m_]:=Union[Sort/@If[Length[m]==0,{{}},Join@@Table[Prepend[#,m[[ipr]]]&/@prptns[Delete[m,List/@ipr]],{ipr,Select[Prepend[{#},1]&/@Select[Range[2,Length[m]],m[[#]]>m[[#-1]]&],UnsameQ@@m[[#]]&]}]]];

%t strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];

%t Table[Length[Select[strnorm[2*n],Select[prptns[#],UnsameQ@@#&]!={}&]],{n,6}] (* _Gus Wiseman_, Oct 26 2018 *)

%Y Cf. A000070, A000219, A004250, A004251, A007717, A025065, A029889, A095268, A096373, A147878, A209816, A320911, A320921, A320922.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_