  Using polynomial equations to model combinatorial problems has been a popular
tool both in computational combinatorics as well as an approach to proving new
theorems. In this paper, we look at several combinatorics problems modeled by
systems of polynomial equations satisfying special properties. If the equations
are infeasible, Hilbert's Nullstellensatz gives a certificate of this fact.
These certificates have been studied and exhibit combinatorial meaning. In this
paper, we generalize some known results and show that the Nullstellensatz
certificate can be viewed as enumerating combinatorial structures. As such,
Gr\"obner basis algorithms for solving these decision problems may implicitly
be solving the enumeration problem as well.
