Counting Baxter matrices

DOI10.37236/10839MaRDI QIDQ2111771zbMATH OpenOpenAlexFDO

Authors George Spahn

Publication date 17 January 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.09688

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Matrix equations and identities (15A24)

Abstract: Donald Knuth 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 1's in a $rimesk$ Baxter matrix is less than $r+k$.

Review text

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\).

Recommendations

• Baxter permutations
• Bijections for Baxter families and related objects
• Baxter posets
• Shuffle of parenthesis systems and Baxter permutations
• Bijective counting of involutive Baxter permutations

Cites work

• Algebraic and combinatorial structures on Baxter permutations
• Baxter permutations and plane bipolar orientations
• On Fixed Points of the Composite of Commuting Functions

Cited in

(2)

• Counting on matrices
• The number of 1s in Baxter matrices

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Counting Baxter matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111771)