vol. 28:1, Permutation Patterns 2025

---

1. Stack-sorting preimages and 0-1-trees

Bona, Miklos.

We define a class of partially labeled trees and use them to find simple proofs for two recent enumeration results of Colin Defant concerning stack-sorting preimages of permutation classes.

---

2. A Pollak Proof for the Number of Weakly Increasing Parking Functions

Harris, Pamela E. ; Mori, J. Carlos Martínez ; Wilson, Alexander N..

We develop a circular-street argument, in the style of Pollak, to obtain a new proof that there are $C_n = \frac{1}{n+1}\binom{2n}{n}$ weakly increasing parking functions of length $n \geq 1$, where $C_n$ is the $n$th Catalan number.

---

3. Pattern avoidance in compositions and powers of permutations

Archer, Kassie ; Bourne, Noel.

A permutation $π$ is said to avoid a chain $(σ:τ)$ of patterns if $π$ avoids $σ$ and $π^2$ avoids $τ.$ In this paper, we define a notion of pattern avoidance for compositions of positive integers and use that idea to enumerate permutations of length $n$ that avoid the chain $(312,321:σ)$ for any pattern $σ\in \bigcup_{m\geq 1} S_m$. We also enumerate those permutations that avoid the chain $(312,4321:σ)$ for any $σ\in S_3.$

---

4. An Erdős--Szekeres type result for words with repeats

Celano, Kyle ; Ollson, Abigail ; Velankar, Niraj ; Yan, Jun.

We prove an Erdős--Szekeres type result for finite words over $\mathbb{N}$ with repeated values. Specifically, we define a \emph{repeat} in a word to be an occurrence of a value which is not its first occurrence. We define an occurrence of a \emph{pattern} $π$ in a word $w$ to be a (not necessarily consecutive) subword of $w$ that is order isomorphic to $π$. In this note, we show that every word with $kn^6+1$ repeats contains one of the following patterns: $0^{k+2}$, $0011\cdots nn$, $nn\cdots1100$, $012 \cdots n012 \cdots n$, $012 \cdots nn\cdots 210$, $n\cdots 210012\cdots n$, $n\cdots 210n\cdots 210$. Moreover, when $k=1$, we show that this is best possible by constructing a word with $n^6$ repeats that does not contain any of these patterns.

---