A339656 Number of loop-graphical integer partitions of 2n.

1, 2, 4, 8, 15, 28, 49, 84, 140, 229, 367, 577, 895, 1368, 2064, 3080, 4547, 6642, 9627, 13825, 19704, 27868, 39164, 54656, 75832, 104584

Offset: 0

Author

Gus Wiseman, Dec 14 2020

Keywords

• nonn
• more

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 two equal vertices. See A339658 for the Heinz numbers, and A339655 for the complement.

The following are equivalent characteristics for any positive integer n:

(1) the multiset of prime factors of n can be partitioned into distinct pairs, i.e., into a set of edges and loops;

(2) n can be factored into distinct semiprimes;

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

Examples

			The a(0) = 1 through a(4) = 15 partitions:
  ()  (2)    (2,2)      (3,3)          (3,3,2)
      (1,1)  (3,1)      (2,2,2)        (4,2,2)
             (2,1,1)    (3,2,1)        (4,3,1)
             (1,1,1,1)  (4,1,1)        (2,2,2,2)
                        (2,2,1,1)      (3,2,2,1)
                        (3,1,1,1)      (3,3,1,1)
                        (2,1,1,1,1)    (4,2,1,1)
                        (1,1,1,1,1,1)  (5,1,1,1)
                                       (2,2,2,1,1)
                                       (3,2,1,1,1)
                                       (4,1,1,1,1)
                                       (2,2,1,1,1,1)
                                       (3,1,1,1,1,1)
                                       (2,1,1,1,1,1,1)
                                       (1,1,1,1,1,1,1,1)
For example, there are four possible loop-graphs with degrees y = (2,2,1,1), namely
  {{1,1},{2,2},{3,4}}
  {{1,1},{2,3},{2,4}}
  {{1,2},{1,3},{2,4}}
  {{1,2},{1,4},{2,3}}
  {{1,3},{1,4},{2,2}},
so y is counted under a(3). On the other hand, there are two possible loop-multigraphs with degrees z = (4,2), namely
  {{1,1},{1,1},{2,2}}
  {{1,1},{1,2},{1,2}},
but neither of these is a loop-graph, so z is not counted under a(3).
		

Links

• Eric Weisstein's World of Mathematics, Graphical partition.

Crossrefs

A339658 ranks these partitions.

A001358 lists semiprimes, with squarefree case A006881.

A006125 counts labeled graphs, with covering case A006129.

A027187 counts partitions of even length, ranked by A028260.

A062740 counts labeled connected loop-graphs.

A320461 ranks normal loop-graphs.

A320655 counts factorizations into semiprimes.

A322353 counts factorizations into distinct semiprimes.

A322661 counts covering loop-graphs.

A339845 counts the same partitions by length, or A339844 with zeros.

The following count vertex-degree partitions and give their Heinz numbers:

- A000070 counts non-multigraphical partitions of 2n (A339620).

- A000569 counts graphical partitions (A320922).

- A058696 counts partitions of 2n (A300061).

- A209816 counts multigraphical partitions (A320924).

- A321728 is conjectured to count non-half-loop-graphical partitions of n.

- A339617 counts non-graphical partitions of 2n (A339618).

- A339655 counts non-loop-graphical partitions of 2n (A339657).

- A339656 [this sequence] counts loop-graphical partitions (A339658).

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. A001055, A001222, A025065, A095268, A101048, A320656, A320921, A338902, A338912, A338913, A339659.

Programs

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}]

Formula

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

Extensions

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