A339843 Number of distinct sorted degree sequences among all n-vertex half-loop-graphs without isolated vertices.

1, 1, 3, 9, 29, 97, 336, 1188, 4275, 15579, 57358, 212908, 795657, 2990221, 11291665, 42814783, 162920417, 621885767, 2380348729

Offset

0,3

Comments

In the covering case, these degree sequences, sorted in decreasing order, are the same thing as half-loop-graphical partitions (A321729). An integer partition is half-loop-graphical if it comprises the multiset of vertex-degrees of some graph with half-loops, where a half-loop is an edge with one vertex.

The following are equivalent characteristics for any positive integer n:

(1) the prime indices of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops or edges;

(2) n can be factored into distinct primes or squarefree semiprimes;

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

Links

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

Eric Weisstein's World of Mathematics, Degree Sequence.

Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Formula

a(n) = A029889(n) - A029889(n-1) for n > 0. - Andrew Howroyd, Jan 10 2024

Example

The a(0) = 1 through a(3) = 9 sorted degree sequences:
  ()  (1)  (1,1)  (1,1,1)
           (2,1)  (2,1,1)
           (2,2)  (2,2,1)
                  (2,2,2)
                  (3,1,1)
                  (3,2,1)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees y = (3,2,2), so y is counted under a(3).

Mathematica

Table[Length[Union[Sort[Table[Count[Join@@#, i], {i, n}]]&/@Select[Subsets[Subsets[Range[n], {1, 2}]], Union@@#==Range[n]&]]], {n, 0, 5}]

Crossrefs

See link for additional cross references.

The version for simple graphs is A004251, covering: A095268.

The non-covering version (it allows isolated vertices) is A029889.

The same partitions counted by sum are conjectured to be A321729.

These graphs are counted by A006125 shifted left, covering: A322661.

The version for full loops is A339844, covering: A339845.

These graphs are ranked by A340018 and A340019.

A006125 counts labeled simple graphs, covering: A006129.

A027187 counts partitions of even length, ranked by A028260.

A058696 counts partitions of even numbers, ranked by A300061.

A320663/A339888 count unlabeled multiset partitions into singletons/pairs.

A339659 counts graphical partitions of 2n into k parts.

Cf. A062740, A096373, A167171, A320461, A320893, A320921, A320923, A338915, A339560, A339841, A339842.

Sequence in context: A071740 A081696 A247172 * A148939 A346158 A077587

Adjacent sequences: A339840 A339841 A339842 * A339844 A339845 A339846

Keyword

nonn,more

Author

Gus Wiseman, Dec 27 2020

Extensions

a(7)-a(18) added (using A029889) by Andrew Howroyd, Jan 10 2024

Status

approved