Counting binary matrices with given row and column sums

Abstract:

This paper is concerned with the calculation of certain numbers $sb(\bar p)$, $b(\bar p,\bar q)$ related to combinatorial problems and graph theory. $\bar p,\bar q$ are vectors of nonnegative integers, and $sb(\bar p)$ is the number of labelled graphs with vertex degree sequence $\bar p$, or equivalently, the number of 0-diagonal, symmetric, binary matrices with row sum $\bar p$. Similarly, $b(\bar p,\bar q)$ is the number of binary rectangular matrices with row sum $\bar p$ and column sum $\bar q$. The numbers also appear as coefficients in the expansions $\Pi (1 + {x_i}{x_j})$, $\Pi (1 + {x_i}{y_j})$. Explicit (i.e., nonrecursive) formulas for $sb(\bar p)$, $b(\bar p,\bar q)$ are developed, together with an analysis of their complexity. Properties of $\bar p$ (or $\bar q$), such as $\max \{ {p_i}\}$, $k = \Sigma {p_i}$, $n = \# \{ {p_i} \ne 0\}$, are incorporated into a numerical invariant which measures the total "cost" (or computing time). The performance of the theory for practical calculations has been thoroughly tested. For example, with suitable restrictions on $\bar p$ one may obtain $sb(\bar p)$ for, say, $n = 20$ or $k = 30$.