login
A339617
Number of non-graphical integer partitions of 2n.
24
0, 1, 3, 6, 13, 25, 46, 81, 141, 234, 383, 615, 968, 1503, 2298, 3468, 5176, 7653, 11178, 16212, 23290, 33218, 46996, 66091, 92277, 128122, 176787, 242674, 331338, 450279, 608832, 819748, 1098907, 1467122, 1951020, 2584796, 3411998
OFFSET
0,3
COMMENTS
An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. See A209816 for multigraphical partitions, A000070 for non-multigraphical partitions. Graphical partitions are counted by A000569.
The following are equivalent characteristics for any positive integer n:
(1) the prime indices of n can be partitioned into distinct strict pairs (a set of edges);
(2) n can be factored into distinct squarefree semiprimes;
(3) the prime signature of n is graphical.
LINKS
Eric Weisstein's World of Mathematics, Graphical partition.
FORMULA
a(n) + A000569(n) = A000041(2*n).
EXAMPLE
The a(1) = 1 through a(4) = 13 partitions:
(2) (4) (6) (8)
(2,2) (3,3) (4,4)
(3,1) (4,2) (5,3)
(5,1) (6,2)
(3,2,1) (7,1)
(4,1,1) (3,3,2)
(4,2,2)
(4,3,1)
(5,2,1)
(6,1,1)
(3,3,1,1)
(4,2,1,1)
(5,1,1,1)
For example, the partition (2,2,2,2) is not counted under a(4) because there are three possible graphs with the prescribed degrees:
{{1,2},{1,3},{2,4},{3,4}}
{{1,2},{1,4},{2,3},{3,4}}
{{1,3},{1,4},{2,3},{2,4}}
MATHEMATICA
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, 0, 5}]
CROSSREFS
A006881 lists squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339659 counts graphical partitions of 2n into k parts.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 [this sequence] counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Sequence in context: A047183 A047194 A048039 * A131913 A182808 A285461
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 13 2020
STATUS
approved