Enumeration of words that contain the pattern 123 exactly once

NEW

Problem: For fixed $r\ge 1$, let $a_r(n)$ be the number of words of length $rn$ on the ordered alphabet $\{1,\dots,n\}$, with each letter appearing exactly $r$ times, and with exactly one subsequence $w_iw_jw_k$ $(i<j<k)$ order-isomorphic to $123$, i.e. $w_i<w_j<w_k$. The conjecture is

$$a_r(n)\sim C_r\bigl((r+1)2^r\bigr)^n n^{-3/2} \qquad(n\to\infty)$$

for some constant $C_r>0$ depending only on $r$.

Result: The conjecture is true.

Let $\mu=(r+1)2^r$. For $0\le s\le r$, let $A_s(m)$ denote the number of $123$-avoiding words whose content consists of $m$ letters of multiplicity $r$, together with one extra distinguished letter of multiplicity $s$. Thus $A_0(m)$ is the usual number of $123$-avoiding words with content $r^m$.

A standard RSK/Jacobi-Trudi calculation gives, uniformly for fixed $s$,

$$A_s(m)\sim \alpha_{r,s}\mu^m m^{-3/2}, \qquad \alpha_{r,s}=2^s(s+1)\alpha_{r,0},$$

where Chapuy’s $d=2$ asymptotic gives

$$\alpha_{r,0}=\frac1{\sqrt\pi}\left(\frac{6}{r(r+5)}\right)^{3/2}.$$

Indeed, for $N=rm+s$,

$$A_s(m)=\sum_{u\le N/2} f_{(N-u,u)}K_{(N-u,u),(r^m,s)},$$

with

$$f_{(N-u,u)}=\frac{N-2u+1}{N-u+1}\binom Nu$$

and

$$K_{(N-u,u),(r^m,s)} =[z^u](1-z)(1+z+\cdots+z^r)^m(1+z+\cdots+z^s).$$

Stirling’s formula and the local central limit theorem show that only $u=N/2+O(\sqrt m)$ contributes, yielding the displayed asymptotic.

Set

$$\Delta_s(m)=A_s(m)-A_{s-1}(m)\qquad(1\le s\le r).$$

Then

$$\Delta_s(m)\sim \beta_{r,s}\mu^m m^{-3/2}, \qquad \beta_{r,s}=\alpha_{r,0}2^{s-1}(s+2)>0.$$

Moreover $\sum_{m\ge1}\Delta_s(m)\mu^{-m}<\infty$.

Yang’s bijective formula for words with exactly one $123$ gives

$$a_r(n)=\sum_{s=1}^r\sum_{k=1}^{n-2} \Delta_s(k)\Delta_{r+1-s}(n-k-1).$$

For sequences $x_k\sim c_x\mu^k k^{-3/2}$, $y_k\sim c_y\mu^k k^{-3/2}$, their convolution satisfies

$$\sum_{k=1}^{n-2}x_k y_{n-k-1} \sim \mu^{n-1}n^{-3/2} \left(c_y\sum_{k\ge1}x_k\mu^{-k} +c_x\sum_{k\ge1}y_k\mu^{-k}\right),$$

because the exponent $3/2>1$ makes the convolution edge-dominated.

Applying this to the displayed formula for $a_r(n)$ gives

$$a_r(n)\sim C_r\mu^n n^{-3/2},$$

where

$$C_r=\mu^{-1}\sum_{s=1}^r \left( \beta_{r,r+1-s}L_s+\beta_{r,s}L_{r+1-s} \right)>0, \qquad L_s=\sum_{m\ge1}\Delta_s(m)\mu^{-m}.$$

Thus

$$a_r(n)\sim C_r\bigl((r+1)2^r\bigr)^n n^{-3/2}.$$

Audit: the reconstructed statement matches Yang’s definition of $a_r(n)$; $r$ is fixed and positive; the pattern is strict $123$; the finitely many small $n$ cases do not affect the asymptotic; no extra hypotheses are introduced.

Citation: M. Yang, “Enumeration of words that contain the pattern $123$ exactly once,” arXiv:1712.08662, Theorem 1.
G. Chapuy, “The asymptotic number of $12\cdots d$-avoiding words with $r$ occurrences of each letter $1,2,\dots,n$,” arXiv:1412.6070, Theorem 1.