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 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 = \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?)

  • [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 $ {\Pi _{i < j}}(1 + {x_i}{x_j})$, 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)

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