cp's OEIS Frontend

A339617 Number of non-graphical integer partitions of 2n.

%I A339617 #9 Feb 16 2025 08:34:01
%S A339617 0,1,3,6,13,25,46,81,141,234,383,615,968,1503,2298,3468,5176,7653,
%T A339617 11178,16212,23290,33218,46996,66091,92277,128122,176787,242674,
%U A339617 331338,450279,608832,819748,1098907,1467122,1951020,2584796,3411998
%N A339617 Number of non-graphical integer partitions of 2n.
%C A339617 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.
%C A339617 The following are equivalent characteristics for any positive integer n:
%C A339617 (1) the prime indices of n can be partitioned into distinct strict pairs (a set of edges);
%C A339617 (2) n can be factored into distinct squarefree semiprimes;
%C A339617 (3) the prime signature of n is graphical.
%H A339617 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphicalPartition.html">Graphical partition.</a>
%F A339617 a(n) + A000569(n) = A000041(2*n).
%e A339617 The a(1) = 1 through a(4) = 13 partitions:
%e A339617   (2)  (4)    (6)      (8)
%e A339617        (2,2)  (3,3)    (4,4)
%e A339617        (3,1)  (4,2)    (5,3)
%e A339617               (5,1)    (6,2)
%e A339617               (3,2,1)  (7,1)
%e A339617               (4,1,1)  (3,3,2)
%e A339617                        (4,2,2)
%e A339617                        (4,3,1)
%e A339617                        (5,2,1)
%e A339617                        (6,1,1)
%e A339617                        (3,3,1,1)
%e A339617                        (4,2,1,1)
%e A339617                        (5,1,1,1)
%e A339617 For example, the partition (2,2,2,2) is not counted under a(4) because there are three possible graphs with the prescribed degrees:
%e A339617   {{1,2},{1,3},{2,4},{3,4}}
%e A339617   {{1,2},{1,4},{2,3},{3,4}}
%e A339617   {{1,3},{1,4},{2,3},{2,4}}
%t A339617 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 A339617 strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
%t A339617 Table[Length[Select[strnorm[2*n],Select[prptns[#],UnsameQ@@#&]=={}&]],{n,0,5}]
%Y A339617 A006881 lists squarefree semiprimes.
%Y A339617 A320656 counts factorizations into squarefree semiprimes.
%Y A339617 A339659 counts graphical partitions of 2n into k parts.
%Y A339617 The following count vertex-degree partitions and give their Heinz numbers:
%Y A339617 - A058696 counts partitions of 2n (A300061).
%Y A339617 - A000070 counts non-multigraphical partitions of 2n (A339620).
%Y A339617 - A209816 counts multigraphical partitions (A320924).
%Y A339617 - A339655 counts non-loop-graphical partitions of 2n (A339657).
%Y A339617 - A339656 counts loop-graphical partitions (A339658).
%Y A339617 - A339617 [this sequence] counts non-graphical partitions of 2n (A339618).
%Y A339617 - A000569 counts graphical partitions (A320922).
%Y A339617 The following count partitions of even length and give their Heinz numbers:
%Y A339617 - A027187 has no additional conditions (A028260).
%Y A339617 - A096373 cannot be partitioned into strict pairs (A320891).
%Y A339617 - A338914 can be partitioned into strict pairs (A320911).
%Y A339617 - A338915 cannot be partitioned into distinct pairs (A320892).
%Y A339617 - A338916 can be partitioned into distinct pairs (A320912).
%Y A339617 - A339559 cannot be partitioned into distinct strict pairs (A320894).
%Y A339617 - A339560 can be partitioned into distinct strict pairs (A339561).
%Y A339617 Cf. A001055, A007717, A025065, A320921, A320922, A338899, A339564, A339619, A339660, A339661.
%K A339617 nonn
%O A339617 0,3
%A A339617 _Gus Wiseman_, Dec 13 2020