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

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

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.

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

Crossrefs

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

Partial sums of A181532.

Sequence in context: A136299 A208354 A003116 * A303666 A260917 A165648

Adjacent sequences: A368296 A368297 A368298 * A368300 A368301 A368302

Keyword

nonn,easy

Author

Kassie Archer, Dec 20 2023

Status

approved