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

About 5 years old · traced to

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

Sn,k=Sn,k−1+2Sn−1,k−Sn−1,k−1,S_{n,k}=S_{n,k-1}+2S_{n-1,k}-S_{n-1,k-1},

for 1≤k≤n−21\leq k\leq n-2, with Sn,n=Sn,n−1=Sn,n−2S_{n,n}=S_{n,n-1}=S_{n,n-2} for n≥3n\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⋯σn∈Sn(ν,μ)∣σn=k}∣S_{n,k}=\left|\{\sigma_1\cdots\sigma_n\in\mathcal{S}_n(\nu,\mu)\mid \sigma_n=k\}\right|

for all 1≤k≤n1\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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.