A363432 Number of 231-avoiding stabilized-interval-free permutations of size n.

1, 1, 1, 1, 2, 6, 18, 54, 170, 551, 1817, 6092, 20722, 71325, 248055, 870402, 3077861, 10959008, 39261382, 141430953, 512002865, 1861872379, 6798330676, 24915934639, 91630864177, 338048560865, 1250793108398, 4640542045919, 17260221009367, 64349394615738, 240434325753052

Offset: 0

Author

Juan B. Gil, Jun 22 2023

Keywords

• nonn

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.

Examples

			For n=5 the a(5)=6 permutations are 51234, 51423, 53124, 54123, 54132, 54213.
		

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.

Crossrefs

Cf. A000108, A075834.

Programs

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

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