Technical Reports
HPL-2011-239
Click here for full text:
Asymptotic Enumeration of Binary Matrices with Bounded Row and Column Weights
Ordentlich, Erik; Parvaresh, Farzad; Roth, Ron M.
HP Laboratories
HPL-2011-239
Keyword(s): Asymptotic enumeration; Laplace's method of integration; Majorization; Weight constrained arrays; two-dimensional coding;
Abstract: Consider the set $\Aset_n$ of all $n \times n$ binary matrices in which the number of $1$'s in each row and column is at most $n/2$. We show that the redundancy, $n^2 - \log_2 Aset_n , of this set equals $\rho n - \delta \sqrt{n} + O(\log n)$, for a constant $\rho \approx 1.42515$, and $\delta = \delta(n) \approx 1.46016$ for even $n$ and $0$ otherwise.
31 Pages
External Posting Date: December 8, 2011 [Fulltext]. Approved for External Publication
Internal Posting Date: December 8, 2011 [Fulltext]