Alternative Approaches for Counting Weakly Increasing Matrices

Abstract

This paper presents two alternative approaches for counting the number of two-row weakly increasing matrices, which are $2\times n$ matrices whose entries are integers from $1$ to $k$ and are weakly increasing along all rows and columns, for any positive integers $n$ and $k$. The first approach establishes a bijection between the set of such matrices and the set of Kekulé structures for certain hexagonal benzenoids. The second approach reduces the problem to counting the number of pairs of non-intersecting lattice paths. These approaches reveal interesting connections between combinatorial problems that arise in different domains.