Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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," Mat. Lapok, v. 11, 1960, pp. 264-274. (Hungarian)
  • 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, 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.
  • 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, Combinatory Analysis I, Cambridge, 1915.
  • 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, Counting the 10-Point Graphs by Partition, Research Report CORR 79-42, Faculty of Math., Univ. of Waterloo, 1979.
  • 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
Similar Articles
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