Distinct flattened partitions avoiding a pattern of length four

Abstract

Let ${\mathcal{P}}_n$ denote the set of distinct permutations of length $n$ that arise from the flattening process applied to the partitions of $[n]=\{1,\dots ,n\}$. In this paper, we consider the problem of avoidance of a single classical pattern of length four by members of ${\mathcal{P}}_n$. Let $p_n(\tau )$ denote the number of members of ${\mathcal{P}}_n$ that avoid the pattern $\tau$. We show that $p_n(\tau )=C_{n-1}$ for all $n\ge 1$ for seven patterns of length four yielding new combinatorial interpretations of the Catalan number sequence. Further, we show that $p_n(\tau )$ corresponds to the binomial transform of Catalan numbers for three other patterns. To establish our results, we suitably refine the counting sequence $p_n(\tau )$ in each case so as to obtain a system of functional equations satisfied by the corresponding generating functions. These functional equations may then be solved explicitly leading to a determination of $p_n(\tau )$ in each case.