Asymptotic Enumeration of Binary Matrices with Bounded Row and Column

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

HP Development Company

关键词: Asymptotic enumeration;    Laplace's method of integration;    Majorization;    Weight constrained arrays;    two-dimensional coding;   

RP-ID  :  HPL-2011-239

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Consider the set $Aset_n$ of all $n imes 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 $ho n - delta sqrt{n} + O(log n)$, for a constant $ho approx 1.42515$, and $delta = delta(n) approx 1.46016$ for even $n$ and $0$ otherwise.