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
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
0.8154289126396179
0 references
0.8035742044448853
0 references
0.7990515232086182
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