cp's OEIS Frontend

A381981 Number of compositions of n avoiding the patterns (1,2,3) and (3,2,1).

%I A381981 #8 Mar 12 2025 09:39:45
%S A381981 1,1,2,4,8,16,30,56,100,173,293,482,779,1232,1928,2972,4546,6894,
%T A381981 10435,15705,23692,35679,53976,81760,124611,190404,292871,452070,
%U A381981 702042,1094034,1713879,2693284,4250165,6724535,10673794,16977795,27070285,43232232,69167372
%N A381981 Number of compositions of n avoiding the patterns (1,2,3) and (3,2,1).
%C A381981 A composition matches a pattern P if some subsequence of the composition has the same order relation as P. For example, (2,3,4), (1,2,4), and (4,4,2,1,7,1,8) all match the pattern (1,2,3).
%F A381981 G.f.: 1 + Sum_{i>0} (x^i/(1-x^i)) + Sum_{i>0} ( Sum_{j>i}  ( Sum_{k>0} ( (A(i,j,k) + B(i,j,k) + C(i,j,k))*(1 + Sum_{u=i+1..j-1} (-1 + 1/(1-x^u)^2 + 2*Sum_{v=u+1..j-1} ( x^(u+v)/((1-x^u)*(1-x^v)) ) ) ) ) ) ), where A(x,i,j,k) = 2*x^((i+j)*k)/((1-x^i)^k * (1-x^j)^k), B(x,i,j,k) = x^(((i+j)*k)+i)/((1-x^i)^(k+1) * (1-x^j)^k), and C(x,i,j,k) = x^(((j+i)*k)+j)/((1-x^i)^k * (1-x^j)^(k+1)).
%e A381981 For n < 6 all compositions are counted.
%e A381981 For n = 6 and 7, the compositions that match either of the forbidden patterns are shown below:
%e A381981  n=6 2 compositions match: (1,2,3) and (3,2,1), giving a(6) = 2^5 - 2 = 30;
%e A381981  n=7 8 compositions match: (1,1,2,3), (1,2,1,3), (1,2,3,1), (1,3,2,1), (3,1,2,1), (3,2,1,1), (1,2,4), and (4,2,1), giving a(7) = 2^6 - 8 = 56.
%o A381981 (PARI)
%o A381981 A(i,j,k) = {2*x^((i+j)*k)/((1-x^i)^k * (1-x^j)^k)}
%o A381981 B(i,j,k) = {x^(((i+j)*k)+i)/((1-x^i)^(k+1) * (1-x^j)^k)}
%o A381981 C(i,j,k) = {x^(((i+j)*k)+j)/((1-x^i)^k * (1-x^j)^(k+1))}
%o A381981 C_x(N) = {my(x='x+O('x^N), h=1+sum(i=1,N,(x^i)/(1-x^i))+sum(i=1,N,sum(j=i+1,N-i,sum(k=1,N-i-j, (A(i,j,k)+B(i,j,k)+C(i,j,k))*(1+sum(u=i+1,j-1,-1+1/(1-x^u)^2+2*sum(v=u+1,j-1, x^(u+v)/((1-x^u)*(1-x^v))))))))); Vec(h)}
%o A381981 C_x(40)
%Y A381981 Cf. A011782, A102726, A128761, A335471, A335473.
%K A381981 nonn
%O A381981 0,3
%A A381981 _John Tyler Rascoe_, Mar 11 2025