A143981 The number of unigraphical partitions of 2m; that is, the number of partitions of 2m which are realizable as the degree sequence of one and only one graph (where loops are not allowed but multiple edges are allowed).

1, 3, 6, 9, 15, 19, 26, 36, 46, 59, 80, 100, 128, 167, 211, 267, 341, 429, 541, 682, 850, 1063, 1327, 1647, 2035, 2520, 3100, 3810, 4669, 5708, 6955, 8468, 10267, 12441, 15026, 18120, 21788, 26175, 31355, 37510, 44769, 53362, 63460, 75384, 89348

Offset

1,2

Links

Table of n, a(n) for n=1..45.

S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. I, J. Soc. Indust. Appl. Math., vol. 10 (1962), 496-506.

S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. II. Uniqueness, J. Soc. Indust. Appl. Math., vol. 11 (1963), 135-147.

Formula

For m >= 3, a(2m) = A000041(m) + A001399(m-3) + A000005(m+1) + A083039(m-2) + m - 5.

Example

For m = 4, the number of unigraphical partitions is A000041(4) + A001399(1) + A000005(5) + A083039(2) + 4 - 5 = 5 + 1 + 2 + 2 + 4 - 5 = 9.

Maple

with(combinat): with(numtheory): a:=proc(m) it:=round(m^2/12)+numbpart(m)+tau(m+1)+m-5: if m mod 6 = 0 then it:=it+2 fi: if m mod 6 = 1 then it:=it+1 fi: if m mod 6 = 2 then it:=it+3 fi: if m mod 6 = 3 then it:=it+1 fi: if m mod 6 = 4 then it:=it+2 fi: if m mod 6 = 5 then it:=it+2 fi: RETURN(it): end:

Crossrefs

Cf. A000041, A001399, A000005, A083039.

Sequence in context: A355498 A049991 A368611 * A031940 A007187 A337502

Adjacent sequences: A143978 A143979 A143980 * A143982 A143983 A143984

Keyword

nonn

Author

Michael David Hirschhorn and James A. Sellers, Sep 06 2008

Status

approved