Technical Reports


Click here for full text: PDF

Asymptotic Enumeration of Binary Matrices with Bounded Row and Column Weights

Ordentlich, Erik; Parvaresh, Farzad; Roth, Ron M.
HP Laboratories


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