A368299 a(n) is the number of permutations pi of [n] that avoid {231,321} so that pi^4 avoids 132.

0, 1, 2, 4, 7, 13, 23, 41, 72, 127, 223, 392, 688, 1208, 2120, 3721, 6530, 11460, 20111, 35293, 61935, 108689, 190736, 334719, 587391, 1030800, 1808928, 3174448, 5570768, 9776017, 17155714, 30106180, 52832663, 92714861, 162703239, 285524281, 501060184, 879299327

Offset: 0

Author

Kassie Archer, Dec 20 2023

Keywords

• nonn
• easy

Comments

Number of compositions of n of the form d_1+d_2+...+d_k=n where d_i is in {1,2,4} if i>1 and d_1 is any positive integer.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000
• Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023.
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1,-1).

Crossrefs

Cf. A000071 (d_i in {1,2}), A077868 (d_i in {1,3}), A274110, A303666.

Partial sums of A181532.

Programs

Maple

a:= proc(n) option remember;
     `if`(n<1, 0, 1+add(a(n-j), j=[1, 2, 4]))
    end:
seq(a(n), n=0..37);  # Alois P. Heinz, Dec 20 2023

Mathematica

LinearRecurrence[{2,0,-1,1,-1},{0,1,2,4,7},38] (* Stefano Spezia, Dec 21 2023 *)

Formula

G.f.: x/((1-x)*(1-x-x^2-x^4)).

a(n) = Sum_{m=0..n-1} Sum_{r=0..floor(m/4)} Sum_{j=0..floor((m-4*r)/2)} binomial(m-3*r-j,r)*binomial(m-4*r-j,j).

a(n) = 1+a(n-1)+a(n-2)+a(n-4) where a(0)=0, a(1)=1, a(2)=2, a(3)=4.

a(n) = A274110(n+1) - 1.