A363433 Number of (123,231)-avoiding stabilized-interval-free permutations of size n.

1, 1, 1, 1, 1, 2, 3, 3, 5, 5, 7, 7, 10, 9, 13, 12, 16, 15, 20, 18, 24, 22, 28, 26, 33, 30, 38, 35, 43, 40, 49, 45, 55, 51, 61, 57, 68, 63, 75, 70, 82, 77, 90, 84, 98, 92, 106, 100, 115, 108, 124, 117, 133, 126, 143, 135, 153, 145, 163, 155, 174, 165, 185, 176, 196

Offset

0,6

Comments

A stabilized-interval-free (SIF) permutation on [n] = {1, 2, ..., n} is one that does not stabilize any proper subinterval of [n].

Links

Paolo Xausa, Table of n, a(n) for n = 0..10000

Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.

Index entries for linear recurrences with constant coefficients, signature (0,2,1,-1,-2,0,1).

Formula

G.f.: (x^9 + x^8 - 3*x^6 - 2*x^5 + x^4 + 2*x^3 + x^2 - x - 1)/((x^2 + x + 1)*(x + 1)^2*(x - 1)^3).

E.g.f.: (144 + 36*x*(2 + x) + (3*x^2 + 15*x - 80)*cosh(x) + 8*exp(-x/2)*(cos(sqrt(3)*x/2) - sqrt(3)*sin(sqrt(3)*x/2)) + (3*x^2 + 33*x + 1)*sinh(x))/72. - Stefano Spezia, Jul 01 2023

144*a(n) = 16*A131713(n) +42*n -79 +6*n^2 -81*(-1)^n +18*n*(-1)^n , for n>=3. - R. J. Mathar, Jul 17 2023

Example

For n from 1 to 5 the six permutations (1+1+1+1+2) are 1, 21, 312, 4312, 54132, 54213.

Maple

A131713 := proc(n)
    op(1+modp(n, 3), [1, -2, 1]) ;
end proc:
A363433 := proc(n)
    if n < 3 then
        1;
    else
        16*A131713(n) +42*n-79+6*n^2-81*(-1)^n+18*n*(-1)^n;
        %/144 ;
    end if;
end proc:
seq(A363433(n), n=0..20) ; # R. J. Mathar, Jul 17 2023

Mathematica

LinearRecurrence[{0, 2, 1, -1, -2, 0, 1}, {1, 1, 1, 1, 1, 2, 3, 3, 5, 5}, 100] (* Paolo Xausa, Nov 18 2023 *)

Prog

(PARI) Vec((x^9 + x^8 - 3*x^6 - 2*x^5 + x^4 + 2*x^3 + x^2 - x - 1)/((x^2 + x + 1)*(x + 1)^2*(x - 1)^3) + O(x^65)) \\ Michel Marcus, Jul 01 2023

Crossrefs

Cf. A075834, A363431, A363432.

Sequence in context: A113637 A257539 A159050 * A387386 A210336 A280271

Adjacent sequences: A363430 A363431 A363432 * A363434 A363435 A363436

Keyword

nonn,easy

Author

Juan B. Gil, Jun 30 2023

Status

approved