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