A368299 - OEIS

%I #42 Jan 16 2024 16:20:10

%S 0,1,2,4,7,13,23,41,72,127,223,392,688,1208,2120,3721,6530,11460,

%T 20111,35293,61935,108689,190736,334719,587391,1030800,1808928,

%U 3174448,5570768,9776017,17155714,30106180,52832663,92714861,162703239,285524281,501060184,879299327

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

%C 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.

%H Alois P. Heinz, <a href="/A368299/b368299.txt">Table of n, a(n) for n = 0..2000</a>

%H Kassie Archer and Aaron Geary, <a href="https://arxiv.org/abs/2312.14351">Powers of permutations that avoid chains of patterns</a>, arXiv:2312.14351 [math.CO], 2023.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,1,-1).

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

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

%F 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.

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

%p a:= proc(n) option remember;

%p      `if`(n<1, 0, 1+add(a(n-j), j=[1, 2, 4]))

%p     end:

%p seq(a(n), n=0..37);  # _Alois P. Heinz_, Dec 20 2023

%t LinearRecurrence[{2,0,-1,1,-1},{0,1,2,4,7},38] (* _Stefano Spezia_, Dec 21 2023 *)

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

%Y Partial sums of A181532.

%K nonn,easy

%O 0,3

%A _Kassie Archer_, Dec 20 2023