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 , related to combinatorial problems and graph theory. are vectors of nonnegative integers, and is the number of labelled graphs with vertex degree sequence , or equivalently, the number of 0-diagonal, symmetric, binary matrices with row sum . Similarly, is the number of binary rectangular matrices with row sum and column sum . The numbers also appear as coefficients in the expansions , .

Explicit (i.e., nonrecursive) formulas for , are developed, together with an analysis of their complexity. Properties of (or ), such as , , , 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 one may obtain for, say, or .

**[1]**J. A. Bondy and U. S. R. Murty,*Graph theory with applications*, American Elsevier Publishing Co., Inc., New York, 1976. MR**0411988****[2]**P. Erdös & T. Gallai, "Graphs with prescribed degrees of vertices,"*Mat. Lapok*, v. 11, 1960, pp. 264-274. (Hungarian)**[3]**Phil Hanlon,*Enumeration of graphs by degree sequence*, J. Graph Theory**3**(1979), no. 3, 295–299. MR**542552**, https://doi.org/10.1002/jgt.3190030313**[4]**Frank Harary and Edgar M. Palmer,*Graphical enumeration*, Academic Press, New York-London, 1973. MR**0357214****[5]**B. Johnsen & E. Straume,*Combinatorial Tables*I.*Evaluation of the Product*, Univ. of Tromsø, 1980.**[6]**B. Johnsen & E. Straume,*Combinatorial Tables*II.*Graphic Monomials*, Univ. of Tromsø, 1981.**[7]**Adalbert Kerber,*Representations of permutation groups. I*, Lecture Notes in Mathematics, Vol. 240, Springer-Verlag, Berlin-New York, 1971. MR**0325752****[8]**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**0123483****[9]**P. A. MacMahon,*Combinatory Analysis*I, Cambridge, 1915.**[10]**R. C. Read,*The enumeration of locally restricted graphs. I*, J. London Math. Soc.**34**(1959), 417–436. MR**0108446**, https://doi.org/10.1112/jlms/s1-34.4.417**[11]**R. C. Read,*The enumeration of locally restricted graphs. II*, J. London Math. Soc.**35**(1960), 344–351. MR**0140443**, https://doi.org/10.1112/jlms/s1-35.3.344**[12]**Ronald C. Read,*The use of 𝑆-functions in combinatorial analysis*, Canad. J. Math.**20**(1968), 808–841. MR**0229534**, https://doi.org/10.4153/CJM-1968-080-x**[13]**Ronald C. Read,*Enumeration*, Graph connections, Oxford Lecture Ser. Math. Appl., vol. 5, Oxford Univ. Press, New York, 1997, pp. 13–33. MR**1634544****[14]**R. C. Read & N. C. Wormald,*Counting the 10-Point Graphs by Partition*, Research Report CORR 79-42, Faculty of Math., Univ. of Waterloo, 1979.**[15]**John Riordan,*Symmetric function expansions of power sum products into monomials and their inverses*, Duke Math. J.**38**(1971), 285–294. MR**0281628****[16]**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****[17]**Ernst Snapper,*Group characters and nonnegative integral matrices*, J. Algebra**19**(1971), 520–535. MR**0284523**, https://doi.org/10.1016/0021-8693(71)90085-8

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