A000569 Number of graphical partitions of 2n.

1, 2, 5, 9, 17, 31, 54, 90, 151, 244, 387, 607, 933, 1420, 2136, 3173, 4657, 6799, 9803, 14048, 19956, 28179, 39467, 54996, 76104, 104802, 143481, 195485, 264941, 357635, 480408, 642723, 856398, 1136715, 1503172, 1980785

Offset

1,2

Comments

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.

Links

T. D. Noe, Table of n, a(n) for n = 1..860. [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 Number of Graphical Partitions is corrected by Wang Kai, Aug 03 2016]

Tiffany M. Barnes and Carla D. Savage, Efficient generation of graphical partitions Discrete Appl. Math. 78 (1997), no. 1-3, 17-26.

T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995).

K. Blum, Bounds on the Number of Graphical Partitions, arXiv:2103.03196 [math.CO], 2021. See Table on p. 7.

P. Erdõs and T. Gallai, Graphs with a given degree of vertices, Mat. Lapok, 11 (1960), 264-274.

P. Erdős and L. B. Richmond, On graphical partitions Combinatorica 13 (1993), no. 1, 57-63.

Axel Kohnert, Dominance Order and Graphical Partitions, Electronic J. Combinatorics, 11 (2004).

Gerard Sierksma and Han Hoogeveen, Seven criteria for integer sequences being graphic, J. Graph Theory 15 (1991), no. 2, 223-231.

Eric Weisstein's World of Mathematics, Graphical partition.

Gus Wiseman, Simple graphs realizing each of the a(6) = 31 graphical partitions of 12.

Index entries for sequences related to graphical partitions

Example

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 ||.
From Gus Wiseman, Oct 26 2018: (Start)
The a(1) = 1 through a(5) = 17 graphical partitions:
  (11)  (211)   (222)     (2222)      (3322)
        (1111)  (2211)    (3221)      (22222)
                (3111)    (22211)     (32221)
                (21111)   (32111)     (33211)
                (111111)  (41111)     (42211)
                          (221111)    (222211)
                          (311111)    (322111)
                          (2111111)   (331111)
                          (11111111)  (421111)
                                      (511111)
                                      (2221111)
                                      (3211111)
                                      (4111111)
                                      (22111111)
                                      (31111111)
                                      (211111111)
                                      (1111111111)
(End)

Mathematica

<< MathWorld`Graphs`
Table[Count[RealizeDegreeSequence /@ Partitions[n], _Graph], {n, 2, 20, 2}]
(* second program *)
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[[#]]&]}]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n], Select[prptns[#], UnsameQ@@#&]!={}&]], {n, 6}] (* Gus Wiseman, Oct 26 2018 *)

Crossrefs

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

Sequence in context: A129696 A082281 A285458 * A292168 A322304 A182992

Adjacent sequences: A000566 A000567 A000568 * A000570 A000571 A000572

Keyword

nonn,nice

Author

N. J. A. Sloane

Status

approved