The transposed Catalan triangle formula for partial-shuffle avoidance classes

The Catalan-triangle formula for partial-shuffle avoidance

The count can be obtained by recording a permutation as a pair of standard Young tableaux. Avoiding $321$ leaves only two-row shapes. For each such shape, a known characterization of partial-shuffle avoidance determines the number of possible insertion tableaux. The resulting sum of ballot numbers telescopes to the proposed formula.

Let $a\ge1$, $b\ge0$, and put $p=a+b-2\ge1$. The partial shuffle $\Pi(a,b)$ consists of the permutations obtained by inserting $a$ into the increasing list $[a+b]\setminus\{a\}$, except for the insertion producing the increasing permutation. Write

$$A_n=\#\operatorname{Av}_n(\Pi(a,b),321).$$

We prove, for every $n\ge2p+1$, that

$$\begin{aligned} A_n&=C_p\binom np -\sum_{h=1}^{p-1}T_{p,h}\binom n{p-1-h},\\ C_p&=\frac1{p+1}\binom{2p}p,\\ T_{p,h}&=\frac{h}{2p-h}\binom{2p-h}p. \end{aligned}$$

This is Conjecture 3.9 of Albert, Searles and Slattery-Holmes, with its sum written over the effective range: terms with $h\ge p$ have a negative lower binomial index and contribute zero. Thus no values outside the finite Catalan triangle need to be evaluated. When $p=1$, the sum is empty.

1. The tableau count

By Theorem 3.3 of the same paper, adjoining the decreasing pattern $321$ preserves the Wilf-equivalence of partial shuffles of equal size. It therefore suffices to count permutations avoiding $\Pi(p+2,0)$ and $321$.

We use the following existing tableau characterization from Bloom and Sagan, Theorems 3.1–3.2 and the proof of Theorem 4.1. Under the Robinson–Schensted correspondence, avoidance of $\Pi(p+2,0)$ depends only on the insertion tableau $P$. If $P$ has a cell in first-row column $p+1$, avoidance is equivalent to every entry below the first row being smaller than the entry of that cell. Equivalently, the first-row entries from column $p+1$ onward form the final interval of largest labels. If the first row has at most $p$ cells, the condition is vacuous.

Indeed, $\Pi(p+2,0)$ is the Knuth class of the row-superstandard tableau of shape $(p+1,1)$. The cited characterization prohibits a $(p+1,2)$-ascending sequence: the entry in cell $(1,p+1)$ followed by a larger entry in a lower row. We use this previously established characterization, rather than merely restricting an arbitrary Schur expansion.

Avoidance of $321$ is equivalent to the insertion and recording tableaux having at most two rows. Their common shape is therefore $(n-j,j)$. Since $n\ge2p+1$, its first row has more than $p$ cells. The characterization forces $j\le p$: otherwise the entry in cell $(2,p+1)$ would exceed the entry in cell $(1,p+1)$.

For $0\le j\le p$, all entries outside the first $p$ cells of the first row and the $j$ cells of the second row are the largest labels, in their forced increasing order. Deleting that tail gives an arbitrary standard Young tableau of shape $(p,j)$ on the labels $1,\ldots,p+j$. Conversely, append $p+j+1,\ldots,n$ to its first row. This is an inverse construction and satisfies the required avoidance condition.

Write $f^{(r,j)}$ for the number of standard Young tableaux of shape $(r,j)$, where $r\ge j\ge0$. The recording tableau is unrestricted within the common shape. The Robinson–Schensted bijection consequently gives the exact identity

$$A_n=\sum_{j=0}^{p}f^{(p,j)}f^{(n-j,j)}.$$

2. Telescoping the ballot numbers

Encoding a two-row tableau by the row containing each successive label gives a ballot word. Reflection at the first prefix with more second-row than first-row entries yields

$$f^{(r,j)}=\binom{r+j}{j}-\binom{r+j}{j-1},$$

where $\binom N{-1}=0$. Put $d_j=f^{(p,j)}$. Substitution in the preceding sum and a shift of index give

$$\begin{aligned} A_n &=\sum_{j=0}^{p}d_j \left(\binom nj-\binom n{j-1}\right)\\ &=d_p\binom np +\sum_{j=0}^{p-1}(d_j-d_{j+1})\binom nj. \end{aligned}$$

The ballot formula gives $d_p=C_p$ and $d_{p-1}=C_p$. More generally,

$$d_j=\frac{p-j+1}{p+1}\binom{p+j}p.$$

Subtracting consecutive terms, for $0\le j\le p-1$, gives

$$d_{j+1}-d_j =\frac{p-j-1}{p+j+1}\binom{p+j+1}p.$$

For $j=p-1$ this is zero. For $0\le j\le p-2$, set $h=p-j-1$. Then $p+j+1=2p-h$, so the difference is exactly $T_{p,h}$. Reindexing the last sum proves

$$A_n=C_p\binom np -\sum_{h=1}^{p-1}T_{p,h}\binom n{p-1-h}.$$

The argument includes $p=1$, where it gives $A_n=n$, and applies to every allowed pair $(a,b)$ by the cited Wilf-equivalence. This proves the full stated formula.