cp's OEIS Frontend

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

%I A188900 #41 Aug 24 2024 06:03:54
%S A188900 1,1,2,4,8,16,31,60,114,215,402,746,1375,2520,4593,8329,15036,27027,
%T A188900 48389,86314,153432,271853,480207,845804,1485703,2603018,4549521,
%U A188900 7933239,13803293,23966682,41530721,71830198,124010381,213725823,367736268,631723139,1083568861
%N A188900 Number of compositions of n that avoid the pattern 12-3.
%C A188900 First differs from the non-dashed version A102726 at a(9) = 215, A102726(9) = 214, due to the composition (1,3,2,3).
%C A188900 The value a(11) = 7464 in Heubach et al. is a typo.
%C A188900 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
%H A188900 Nathaniel Johnston, <a href="/A188900/b188900.txt">Table of n, a(n) for n = 0..200</a>
%H A188900 S. Heubach, T. Mansour and A. O. Munagi, <a href="https://web.math.rochester.edu/misc/ojac/vol4/CompType21.pdf">Avoiding Permutation Patterns of Type (2,1) in Compositions</a>, Online Journal of Analytic Combinatorics, 4 (2009).
%F A188900 G.f.: Product_{i>=1} (1/(1 - x^i/Product_{j=1..i-1} (1 - x^j))).
%F A188900 a(n) = 2^(n-1) - A375406(n). - _Gus Wiseman_, Aug 22 2024
%e A188900 The initial terms are too dense, but see A375406 for the complement. - _Gus Wiseman_, Aug 21 2024
%p A188900 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);
%t A188900 m = 35;
%t A188900 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 *)
%t A188900 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], LessEqual@@First/@Split[#,GreaterEqual]&]],{n,0,15}] (* _Gus Wiseman_, Aug 21 2024 *)
%Y A188900 The non-dashed version A102726, non-ranks A335483.
%Y A188900 For 23-1 we have A189076.
%Y A188900 The non-ranks are a subset of A335479 and do not include 404, 788, 809, ...
%Y A188900 For strictly increasing leaders we have A358836, ranks A326533.
%Y A188900 The strict version is A374762.
%Y A188900 The complement is counted by A375406.
%Y A188900 A003242 counts anti-run compositions, ranks A333489.
%Y A188900 A011782 counts compositions.
%Y A188900 A238130, A238279, A333755 count compositions by number of runs.
%Y A188900 A335456 counts patterns matched by compositions.
%Y A188900 Cf. A106356, A188920, A238343, A261982, A333175, A333213, A374630, A374679, A374688, A374740, A374741.
%K A188900 nonn
%O A188900 0,3
%A A188900 _Nathaniel Johnston_, Apr 17 2011