|
|
A000569
|
|
Number of graphical partitions of 2n.
|
|
79
|
|
|
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.
|
|
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]
|
|
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 ||.
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.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|