## Counting binary matrices with given row and column sums

HTML articles powered by AMS MathViewer

- by Ben Johnsen and Eldar Straume PDF
- Math. Comp.
**48**(1987), 737-750 Request permission

## 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

- J. A. Bondy and U. S. R. Murty,
*Graph theory with applications*, American Elsevier Publishing Co., Inc., New York, 1976. MR**0411988**
P. Erdös & T. Gallai, "Graphs with prescribed degrees of vertices," - Phil Hanlon,
*Enumeration of graphs by degree sequence*, J. Graph Theory**3**(1979), no. 3, 295–299. MR**542552**, DOI 10.1002/jgt.3190030313 - Frank Harary and Edgar M. Palmer,
*Graphical enumeration*, Academic Press, New York-London, 1973. MR**0357214**
B. Johnsen & E. Straume, - Adalbert Kerber,
*Representations of permutation groups. I*, Lecture Notes in Mathematics, Vol. 240, Springer-Verlag, Berlin-New York, 1971. MR**0325752** - Jack Levine,
*Coefficient identities derived from expansions of elementary symmetric function products in terms of power sums*, Duke Math. J.**28**(1961), 89–106. MR**123483**
P. A. MacMahon, - R. C. Read,
*The enumeration of locally restricted graphs. I*, J. London Math. Soc.**34**(1959), 417–436. MR**108446**, DOI 10.1112/jlms/s1-34.4.417 - R. C. Read,
*The enumeration of locally restricted graphs. II*, J. London Math. Soc.**35**(1960), 344–351. MR**140443**, DOI 10.1112/jlms/s1-35.3.344 - Ronald C. Read,
*The use of $S$-functions in combinatorial analysis*, Canadian J. Math.**20**(1968), 808–841. MR**229534**, DOI 10.4153/CJM-1968-080-x - Ronald C. Read,
*Enumeration*, Graph connections, Oxford Lecture Ser. Math. Appl., vol. 5, Oxford Univ. Press, New York, 1997, pp. 13–33. MR**1634544**
R. C. Read & N. C. Wormald, - John Riordan,
*Symmetric function expansions of power sum products into monomials and their inverses*, Duke Math. J.**38**(1971), 285–294. MR**281628** - Herbert John Ryser,
*Combinatorial mathematics*, The Carus Mathematical Monographs, No. 14, Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963. MR**0150048** - Ernst Snapper,
*Group characters and nonnegative integral matrices*, J. Algebra**19**(1971), 520–535. MR**284523**, DOI 10.1016/0021-8693(71)90085-8

*Mat. Lapok*, v. 11, 1960, pp. 264-274. (Hungarian)

*Combinatorial Tables*I.

*Evaluation of the Product*${\Pi _{i < j}}(1 + {x_i}{x_j})$, Univ. of Tromsø, 1980. B. Johnsen & E. Straume,

*Combinatorial Tables*II.

*Graphic Monomials*, Univ. of Tromsø, 1981.

*Combinatory Analysis*I, Cambridge, 1915.

*Counting the 10-Point Graphs by Partition*, Research Report CORR 79-42, Faculty of Math., Univ. of Waterloo, 1979.

## Additional Information

- © Copyright 1987 American Mathematical Society
- 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