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

1, 1, 2, 4, 8, 16, 30, 56, 100, 173, 293, 482, 779, 1232, 1928, 2972, 4546, 6894, 10435, 15705, 23692, 35679, 53976, 81760, 124611, 190404, 292871, 452070, 702042, 1094034, 1713879, 2693284, 4250165, 6724535, 10673794, 16977795, 27070285, 43232232, 69167372

Offset: 0

Author

John Tyler Rascoe, Mar 11 2025

Keywords

• nonn

Comments

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

Examples

			For n < 6 all compositions are counted.
For n = 6 and 7, the compositions that match either of the forbidden patterns are shown below:
 n=6 2 compositions match: (1,2,3) and (3,2,1), giving a(6) = 2^5 - 2 = 30;
 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.
		

Crossrefs

Cf. A011782, A102726, A128761, A335471, A335473.

Programs

PARI

A(i,j,k) = {2*x^((i+j)*k)/((1-x^i)^k * (1-x^j)^k)}
B(i,j,k) = {x^(((i+j)*k)+i)/((1-x^i)^(k+1) * (1-x^j)^k)}
C(i,j,k) = {x^(((i+j)*k)+j)/((1-x^i)^k * (1-x^j)^(k+1))}
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)}
C_x(40)

Formula

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