login
A188900
Number of compositions of n that avoid the pattern 12-3.
20
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,3
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
LINKS
S. Heubach, T. Mansour and A. O. Munagi, Avoiding Permutation Patterns of Type (2,1) in Compositions, Online Journal of Analytic Combinatorics, 4 (2009).
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
EXAMPLE
The initial terms are too dense, but see A375406 for the complement. - Gus Wiseman, Aug 21 2024
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 *)
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.
Sequence in context: A362063 A309982 A102726 * A189075 A345372 A189077
KEYWORD
nonn
AUTHOR
Nathaniel Johnston, Apr 17 2011
STATUS
approved