# Technical Reports

## HPL-2011-239

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]

Back to Index