A339655 Number of non-loop-graphical integer partitions of 2n.

0, 0, 1, 3, 7, 14, 28, 51, 91, 156, 260, 425, 680, 1068, 1654, 2524, 3802, 5668, 8350, 12190, 17634, 25306, 36011, 50902, 71441, 99642

Offset

0,4

Comments

An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with equal source and target. See A339657 for the Heinz numbers, and A339656 for the complement.

The following are equivalent characteristics for any positive integer n:

(1) the prime factors of n can be partitioned into distinct pairs;

(2) n can be factored into distinct semiprimes;

(3) the prime signature of n is loop-graphical.

Links

Table of n, a(n) for n=0..25.

Eric Weisstein's World of Mathematics, Graphical partition.

Formula

A058696(n) = a(n) + A339656(n).

Example

The a(2) = 1 through a(5) = 14 partitions (A = 10):
  (4)  (6)    (8)      (A)
       (4,2)  (4,4)    (5,5)
       (5,1)  (5,3)    (6,4)
              (6,2)    (7,3)
              (7,1)    (8,2)
              (5,2,1)  (9,1)
              (6,1,1)  (5,3,2)
                       (5,4,1)
                       (6,2,2)
                       (6,3,1)
                       (7,2,1)
                       (8,1,1)
                       (6,2,1,1)
                       (7,1,1,1)
For example, the seven normal loop-multigraphs with degrees y = (5,3,2) are:
  {{1,1},{1,1},{1,2},{2,2},{3,3}}
  {{1,1},{1,1},{1,2},{2,3},{2,3}}
  {{1,1},{1,1},{1,3},{2,2},{2,3}}
  {{1,1},{1,2},{1,2},{1,2},{3,3}}
  {{1,1},{1,2},{1,2},{1,3},{2,3}}
  {{1,1},{1,2},{1,3},{1,3},{2,2}}
  {{1,2},{1,2},{1,2},{1,3},{1,3}},
but since none of these is a loop-graph (because they are not strict), y is counted under a(5).

Mathematica

spsbin[{}]:={{}}; spsbin[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@spsbin[Complement[set, s]]]/@Cases[Subsets[set], {i, _}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@spsbin[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n], Select[mpsbin[#], UnsameQ@@#&]=={}&]], {n, 0, 5}]

Crossrefs

A001358 lists semiprimes, with squarefree case A006881.

A006125 counts labeled graphs, with covering case A006129.

A062740 counts labeled connected loop-graphs.

A101048 counts partitions into semiprimes.

A320461 ranks normal loop-graphs.

A322661 counts covering loop-graphs.

A320655 counts factorizations into semiprimes.

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 (this sequence) counts non-loop-graphical partitions of 2n (A339657).

- A339656 counts loop-graphical partitions (A339658).

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

Cf. A007717, A025065, A147878, A320732, A320921, A338898, A338902, A338912, A338913, A339659, A339660, A339662.

Sequence in context: A029879 A018084 A285447 * A140741 A088209 A089074

Adjacent sequences: A339652 A339653 A339654 * A339656 A339657 A339658

Keyword

nonn,more

Author

Gus Wiseman, Dec 14 2020

Extensions

a(7)-a(25) from Andrew Howroyd, Jan 10 2024

Status

approved