Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums

Catherine Greenhill*, Brendan D. McKay

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    28 Citations (Scopus)

    Abstract

    Let s = (s1, ..., sm) and t = (t1, ..., tn) be vectors of nonnegative integer-valued functions of m, n with equal sum S = ∑i = 1m si = ∑j = 1n tj. Let M (s, t) be the number of m × n matrices with nonnegative integer entries such that the ith row has row sum si and the jth column has column sum tj for all i, j. Such matrices occur in many different settings, an important example being the contingency tables (also called frequency tables) important in statistics. Define s = maxi si and t = maxj tj. Previous work has established the asymptotic value of M (s, t) as m, n → ∞ with s and t bounded (various authors independently, 1971-1974), and when all entries of s equal s, all entries of t equal t, and m / n, n / m, s / n ≥ c / log n for sufficiently large c [E.R. Canfield, B.D. McKay, Asymptotic enumeration of integer matrices with large equal row and column sums, submitted for publication, 2007]. In this paper we extend the sparse range to the case s t = o (S2 / 3). The proof in part follows a previous asymptotic enumeration of 0-1 matrices under the same conditions [C. Greenhill, B.D. McKay, X. Wang, Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums, J. Combin. Theory Ser. A, 113 (2006) 291-324]. We also generalise the enumeration to matrices over any subset of the nonnegative integers that includes 0 and 1.

    Original languageEnglish
    Pages (from-to)459-481
    Number of pages23
    JournalAdvances in Applied Mathematics
    Volume41
    Issue number4
    DOIs
    Publication statusPublished - Oct 2008

    Fingerprint

    Dive into the research topics of 'Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums'. Together they form a unique fingerprint.

    Cite this