Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Counting binary matrices with given row and column sums


Authors: Ben Johnsen and Eldar Straume
Journal: Math. Comp. 48 (1987), 737-750
MSC: Primary 05A15; Secondary 05B20, 05C30
DOI: https://doi.org/10.1090/S0025-5718-1987-0878703-6
MathSciNet review: 878703
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 05A15, 05B20, 05C30

Retrieve articles in all journals with MSC: 05A15, 05B20, 05C30


Additional Information

Article copyright: © Copyright 1987 American Mathematical Society