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

- 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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, Published by The 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 https://doi.org/10.1016/0021-8693%2871%2990085-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.

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