The general formula for pattern-avoiding stabilized-interval-free permutations

Let fn,d(2)(123)f_{n,d}^{(2)}(123) denote the number of permutations of size nn that avoid the pattern 123123 and have stabilized interval parameter dd. Write n=2m+rn=2m+r with r{0,1}r\in\{0,1\} and let 1dm1\le d\le m. The general enumeration formula.

fn,d(2)(123)=(ndm)2(nd)2[(2dd)d3(1r)4d2+2 ⁣i=1\floorm+13(mir)(md+ri)(2d22i1+dr)(m+im)(md+imd+r)(d2(2ir)2)].f_{n,d}^{(2)}(123) = \frac{\binom{n-d}{m}^2}{(n-d)^2} \Bigg[\frac{\binom{2d}{d}d^3(1-r)}{4d-2} + 2\!\sum_{i=1}^{\floor{\frac{m+1}{3}}}\frac{\binom{m}{i-r}\binom{m-d+r}{i}\binom{2d-2}{2i-1+d-r}}{\binom{m+i}{m}\binom{m-d+i}{m-d+r}}(d^2-(2i-r)^2)\Bigg].

This formula gives a closed expression for the enumeration in all allowed cases, extending the explicitly computed extreme cases d=1d=1 and d=\floorn/2d=\floor{n/2}. The parser provides no evidence resolving whether the asserted formula is proved or remains conjectural.

Sources & referencesView supporting material

Primary source

Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell and Michael D. Weiner, “Pattern-avoiding stabilized-interval-free permutations”, arXiv:2306.03155 (2024).

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.