A029889 Number of graphical partitions (degree-vectors for graphs with n vertices, allowing self-loops which count as degree 1; or possible ordered row-sum vectors for a symmetric 0-1 matrix).

1, 2, 5, 14, 43, 140, 476, 1664, 5939, 21518, 78876, 291784, 1087441, 4077662, 15369327, 58184110, 221104527, 842990294, 3223339023

Offset

0,2

Comments

I call loops of degree one half-loops, so these are half-loop-graphs or graphs with half-loops. - Gus Wiseman, Dec 31 2020

References

R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

Links

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

T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995).

Eric Weisstein's World of Mathematics, Degree Sequence.

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

Index entries for sequences related to graphical partitions

Formula

Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.

a(n) = A029890(n) + A029891(n). - Andrew Howroyd, Apr 18 2021

Example

From Gus Wiseman, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 14 sorted degree sequences:
  ()  (0)  (0,0)  (0,0,0)
      (1)  (1,0)  (1,0,0)
           (1,1)  (1,1,0)
           (2,1)  (2,1,0)
           (2,2)  (2,2,0)
                  (1,1,1)
                  (2,1,1)
                  (3,1,1)
                  (2,2,1)
                  (3,2,1)
                  (2,2,2)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graph
  {{1,3},{3}}
has degrees (1,0,2), so (2,1,0) is counted under a(3). The half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees (3,2,2), so (3,2,2) is counted under a(3).
(End)

Mathematica

Table[Length[Union[Sort[Table[Count[Join@@#, i], {i, n}]]&/@Subsets[Subsets[Range[n], {1, 2}]]]], {n, 0, 5}] (* Gus Wiseman, Dec 31 2020 *)

Crossrefs

Cf. A000569, A004250, A029890, A029891.

Non-half-loop-graphical partitions are conjectured to be counted by A321728.

The covering case (no zeros) is A339843.

MM-numbers of half-loop-graphs are given by A340018 and A340019.

A004251 counts degree sequences of graphs, with covering case A095268.

A320663 counts unlabeled multiset partitions into singletons/pairs.

A339659 is a triangle counting graphical partitions.

A339844 counts degree sequences of loop-graphs, with covering case A339845.

Cf. A006125, A006129, A027187, A028260, A062740, A096373, A322661, A339560.

Sequence in context: A276989 A272461 A213264 * A307787 A221586 A258312

Adjacent sequences: A029886 A029887 A029888 * A029890 A029891 A029892

Keyword

nonn,more

Author

torsten.sillke(AT)lhsystems.com

Extensions

a(0) = 1 prepended by Gus Wiseman, Dec 31 2020

Status

approved