Counting Binary Matrices with Given Row and Column Sums (Q3029028)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4016931
Language Label Description Also known as
default for all languages
No label defined
    English
    Counting Binary Matrices with Given Row and Column Sums
    scientific article; zbMATH DE number 4016931

      Statements

      0 references
      0 references
      1987
      0 references
      enumeration
      0 references
      labelled graphs
      0 references
      binary matrices
      0 references
      Counting Binary Matrices with Given Row and Column Sums (English)
      0 references
      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 \(\prod (1+x_ ix_ j)\), \(\prod (1+x_ iy_ 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=\sum p_ i\), \(n=\#\{p_ i\neq 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\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references