Lin and Kim's refinement conjecture for Schröder numbers

From papers

Let Sn,kS_{n,k} be the triangle defined by

Sn,k=Sn,k1+2Sn1,kSn1,k1,S_{n,k}=S_{n,k-1}+2S_{n-1,k}-S_{n-1,k-1},

for 1kn21\leq k\leq n-2, with Sn,n=Sn,n1=Sn,n2S_{n,n}=S_{n,n-1}=S_{n,n-2} for n3n\geq 3 and S1,1=S2,1=S2,2=1S_{1,1}=S_{2,1}=S_{2,2}=1. For a pair of patterns (ν,μ)(\nu,\mu), let Sn(ν,μ)\mathcal{S}_n(\nu,\mu) denote the permutations in Sn\mathcal{S}_n avoiding both patterns. Lin and Kim's conjecture. Let (ν,μ)(\nu,\mu) be a pair of patterns of length four. Then

Sn,k={σ1σnSn(ν,μ)σn=k}S_{n,k}=\left|\{\sigma_1\cdots\sigma_n\in\mathcal{S}_n(\nu,\mu)\mid \sigma_n=k\}\right|

for all 1kn1\leq k\leq n if and only if (ν,μ)(\nu,\mu) is one of the following nine pairs:

(4321,3421), (3241,2341), (2431,2341), (4231,3241), (4231,2431),(4321,3421),\ (3241,2341),\ (2431,2341),\ (4231,3241),\ (4231,2431), (4231,3421), (2431,3241), (3421,2431), (3421,3241).(4231,3421),\ (2431,3241),\ (3421,2431),\ (3421,3241).

Lin and Kim's conjecture proposes a precise refinement of the Schröder-number enumeration, identifying exactly the two-pattern avoidance classes whose last-entry distribution is given by the triangle Sn,kS_{n,k}. The source presents it as a conjecture, and no resolution is supplied here.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Toufik Mansour and Mark Shattuck, “On a conjecture of Lin and Kim concerning a refinement of Schröder numbers”, arXiv:2104.04491 (2021).

Solutions 0

No solutions have been posted yet.