OFFSET
0,5
COMMENTS
A stabilized-interval-free (SIF) permutation on [n] = {1, 2, ..., n} is one that does not stabilize any proper subinterval of [n].
a(n) is also the number of 312-avoiding SIF permutations of size n.
LINKS
Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
FORMULA
G.f.: 1 + x/(1+C(1)*x^2*(x+1)-x/(1+C(2)*x^3*(x+1)-x/(1+C(3)*x^4*(x+1)-x/(...)))), where C(k)=binomial(2*k,k)/(k+1).
EXAMPLE
For n=5 the a(5)=6 permutations are 51234, 51423, 53124, 54123, 54132, 54213.
MATHEMATICA
nmax = 30; CoefficientList[Series[1 + x/(1 + CatalanNumber[1]*x^2*(x + 1) + ContinuedFractionK[-x, 1 + CatalanNumber[k]*x^(k + 1)*(x + 1), {k, 2, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jun 23 2023 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Juan B. Gil, Jun 22 2023
STATUS
approved