科技报告详细信息
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.
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201804100002802LZ | 256KB | download |