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

At least 2 years old · documented by

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 1≤d≤m1\le d\le m. The general enumeration formula.

fn,d(2)(123)=(n−dm)2(n−d)2[(2dd)d3(1−r)4d−2+2 ⁣∑i=1\floorm+13(mi−r)(m−d+ri)(2d−22i−1+d−r)(m+im)(m−d+im−d+r)(d2−(2i−r)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.

References

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.