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
Examples
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)
References
- R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.
Links
- 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
Crossrefs
Programs
-
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 *)
Formula
Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.
Extensions
a(0) = 1 prepended by Gus Wiseman, Dec 31 2020
Comments