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 , 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 & U. S. R. Murty,*Graph Theory with Applications*, American Elsevier, New York, 1976. MR**0411988 (54:117)****[2]**P. Erdös & T. Gallai, "Graphs with prescribed degrees of vertices,"*Mat. Lapok*, v. 11, 1960, pp. 264-274. (Hungarian)**[3]**P. Hanlon, "Enumeration of graphs by degree sequence,"*J. Graph Theory*, v. 3, 1979, pp. 295-299. MR**542552 (80m:05057)****[4]**F. Harary & E. Palmer,*Graphical Enumeration*, Academic Press, New York, 1973. MR**0357214 (50:9682)****[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]**A. Kerber,*Representation of Permutation Groups*I, Springer-Verlag, Berlin and New York, 1971. MR**0325752 (48:4098)****[8]**J. Levine, "Coefficient identities derived from expansions of elementary symmetric function products in terms of power sums,"*Duke Math. J.*, v. 28, 1961, pp. 89-106. MR**0123483 (23:A808)****[9]**P. A. MacMahon,*Combinatory Analysis*I, Cambridge, 1915.**[10]**R. C. Read, "The enumeration of locally restricted graphs I,"*J. London Math. Soc.*, v. 34, 1959, pp. 417-436. MR**0108446 (21:7162)****[11]**R. C. Read, "The enumeration of locally restricted graphs II,"*J. London Math. Soc.*, v. 35, 1960, pp. 344-351. MR**0140443 (25:3863)****[12]**R. C. Read, "The use of*S*-functions in combinatorial analysis,"*Canad. J. Math.*, v. 20, 1968, pp. 808-841. MR**0229534 (37:5108)****[13]**R. C. Read & N. C. Wormald,*Enumeration of Unlabelled Graphs on 6 to 10 Vertices According to Partition*, Research Report CORR 79-33, Faculty of Math., Univ. of Waterloo, 1979. 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]**J. Riordan, "Symmetric function expansions of power sum products into monomials and their inverses,"*Duke Math. J.*, v. 38, 1971, pp. 285-294. MR**0281628 (43:7343)****[16]**H. J. Ryser,*Combinatorial Mathematics*, Wiley, New York, 1965. MR**0150048 (27:51)****[17]**E. Snapper, "Group characters and nonnegative integral matrices,"*J. Algebra*, v. 19, 1971, pp. 520-535. MR**0284523 (44:1748)**

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