login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000569 Number of graphical partitions of 2n. 50
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 (list; graph; refs; listen; history; text; internal format)
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.

REFERENCES

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

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).

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 20:44 EST 2020. Contains 332111 sequences. (Running on oeis4.)