Determinants, permanents, and the enumeration of forest-partitions

First, we observe that one can regard the domain of the classical partition function p(n) to be the paths P n on n vertices. Replacing P n with an arbitrary tree Tn on n vertices (or any graph Gn on n vertices), we get a more general enumerative function that we call a forest-partition function. We evaluate this function for certain classes of trees, and also obtain some basic properties. Zeilberger has given a combinatorial proof of Dodgson's rule for calculating determinants. By use of Muirs law of extensible minors, Dodgson's rule can be generalized to an identity we call the Dodgson/Muir identity. We give a combinatorial proof of this identity which extends Zeilberger's proof. In the final chapter, we observe how a problem of Polya leads naturally to the study of SNS and convertible matrices. A convertible matrix allows one to compute the permanent (a notoriously difficult computational problem) by a determinant (a computationally easy problem) by using a signing of the matrix. We then construct a sequence of maximal convertible matrices which achieve a new bound for the number of nonzero entries relative to the size of the matrix. Finally, using more than one matrix to convert the permanent problem into one involving determinants, we discuss the notion of m-convertibility. Then, relaxing the requirement that we look at signings of the original matrix, we investigate the example of Jn and convert its permanent in a more general way.