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,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

Table of n, a(n) for n=0..30.

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

Cf. A000108, A075834.

Sequence in context: A114464 A007206 A062415 * A086680 A275872 A148455

Adjacent sequences: A363429 A363430 A363431 * A363433 A363434 A363435

Keyword

nonn

Author

Juan B. Gil, Jun 22 2023

Status

approved