Counting Baxter matrices (Q2111771)

Summary: \textit{D. Knuth} [``Baxter matrices'', Preprint, \url{https://www-cs-faculty.stanford.edu/~knuth/papers/baxter-matrices.pdf}] recently introduced the notion of a Baxter matrix, generalizing Baxter permutations. We show that for fixed number of rows, \(r\), the number of Baxter matrices with \(r\) rows and \(k\) columns eventually satisfies a polynomial in \(k\) of degree \(2r-2\). We also give a proof of Knuth's conjecture that the number of 1s in an \(r \times k\) Baxter matrix is less than \(r+k\).