On the Number of Graphical Forest Partitions

Abstract

A graphical partition of the even integer $n$ is a partition of $n$ where each part of the partition is the degree of a vertex in a simple graph and the degree sum of the graph is $n$. In this note, we consider the problem of enumerating a subset of these partitions, known as graphical forest partitions, graphical partitions whose parts are the degrees of the vertices of forests (disjoint unions of trees). We shall prove that

$$gf(2k)=p(0)+p(1)+p(2)+\cdots +p(k-1)$$

where $g_f(2k)$ is the number of graphical forest partitions of $2k$ and $p(j)$ is the ordinary partition function which counts the number of integer partitions of $j$.