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

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 = \char93 \{ {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

DOI: https://doi.org/10.1090/S0025-5718-1987-0878703-6
Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society