A188900 Number of compositions of n that avoid the pattern 12-3.

1, 1, 2, 4, 8, 16, 31, 60, 114, 215, 402, 746, 1375, 2520, 4593, 8329, 15036, 27027, 48389, 86314, 153432, 271853, 480207, 845804, 1485703, 2603018, 4549521, 7933239, 13803293, 23966682, 41530721, 71830198, 124010381, 213725823, 367736268, 631723139, 1083568861

Offset: 0

Author

Nathaniel Johnston, Apr 17 2011

Keywords

• nonn

Comments

First differs from the non-dashed version A102726 at a(9) = 215, A102726(9) = 214, due to the composition (1,3,2,3).

The value a(11) = 7464 in Heubach et al. is a typo.

Theorem: A composition avoids 3-12 iff its leaders of maximal weakly decreasing runs are weakly increasing. For example, the composition q = (1,1,2,1,2,2,1,3) has maximal weakly decreasing runs ((1,1),(2,1),(2,2,1),(3)), with leaders (1,2,2,3), which are weakly increasing, so q is counted under a(13); also q avoids 3-12, as required. On the other hand, the composition q = (3,2,1,2,2,1,2) has maximal weakly decreasing runs ((3,2,1),(2,2,1),(2)), with leaders (3,2,2), which are not weakly increasing, so q is not counted under a(13); also q matches 3-12, as required. - Gus Wiseman, Aug 21 2024

Examples

			The initial terms are too dense, but see A375406 for the complement. - _Gus Wiseman_, Aug 21 2024
		

Links

• Nathaniel Johnston, Table of n, a(n) for n = 0..200
• S. Heubach, T. Mansour and A. O. Munagi, Avoiding Permutation Patterns of Type (2,1) in Compositions, Online Journal of Analytic Combinatorics, 4 (2009).

Crossrefs

The non-dashed version A102726, non-ranks A335483.

For 23-1 we have A189076.

The non-ranks are a subset of A335479 and do not include 404, 788, 809, ...

For strictly increasing leaders we have A358836, ranks A326533.

The strict version is A374762.

The complement is counted by A375406.

A003242 counts anti-run compositions, ranks A333489.

A011782 counts compositions.

A238130, A238279, A333755 count compositions by number of runs.

A335456 counts patterns matched by compositions.

Cf. A106356, A188920, A238343, A261982, A333175, A333213, A374630, A374679, A374688, A374740, A374741.

Programs

Maple

with(PolynomialTools):n:=20:taypoly:=taylor(mul(1/(1 - x^i/mul(1-x^j,j=1..i-1)),i=1..n),x=0,n+1):seq(coeff(taypoly,x,m),m=0..n);

Mathematica

m = 35;
Product[1/(1 - x^i/Product[1 - x^j, {j, 1, i - 1}]), {i, 1, m}] + O[x]^m // CoefficientList[#, x]& (* Jean-François Alcover, Mar 31 2020 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], LessEqual@@First/@Split[#,GreaterEqual]&]],{n,0,15}] (* Gus Wiseman, Aug 21 2024 *)

Formula

G.f.: Product_{i>=1} (1/(1 - x^i/Product_{j=1..i-1} (1 - x^j))).

a(n) = 2^(n-1) - A375406(n). - Gus Wiseman, Aug 22 2024