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

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

Links

Table of n, a(n) for n=0..38.

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

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A347775 A075529 A005305 * A298402 A125548 A227298

Adjacent sequences: A381978 A381979 A381980 * A381982 A381983 A381984

Keyword

nonn

Author

John Tyler Rascoe, Mar 11 2025

Status

approved