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

Author

Juan B. Gil, Jun 30 2023

Keywords

• nonn
• easy

Comments

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

Examples

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

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

Crossrefs

Cf. A075834, A363431, A363432.

Programs

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

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

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