A189076 - OEIS

%I #39 Aug 22 2024 09:18:21

%S 1,1,2,4,8,16,31,61,118,228,440,846,1623,3111,5955,11385,21752,41530,

%T 79250,151161,288224,549408,1047034,1995000,3800662,7239710,13789219,

%U 26261678,50012275,95237360,181350695,345315255,657506300,1251912618,2383636280,4538364446

%N Number of compositions of n that avoid the pattern 23-1.

%C Note that an exponentiation ^(-1) is missing in Example 4.4. The notation in Theorem 4.3 is complete.

%C Theorem: The reverse of a composition avoids 23-1 iff its leaders of maximal weakly increasing runs are weakly decreasing. For example, the composition y = (3,2,1,2,2,1,2,5,1,1,1) has maximal weakly increasing runs ((3),(2),(1,2,2),(1,2,5),(1,1,1)), with leaders (3,2,1,1,1), which are weakly decreasing, so the reverse of y is counted under a(21). - _Gus Wiseman_, Aug 19 2024

%H Alois P. Heinz, <a href="/A189076/b189076.txt">Table of n, a(n) for n = 0..300</a>

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>.

%H Gus Wiseman, <a href="/A374629/a374629.txt">Sequences counting and ranking compositions by their leaders (for six types of runs)</a>.

%e From _Gus Wiseman_, Aug 19 2024: (Start)

%e The a(6) = 31 compositions:

%e   .  (6)  (5,1)  (4,1,1)  (3,1,1,1)  (2,1,1,1,1)  (1,1,1,1,1,1)

%e           (1,5)  (1,4,1)  (1,3,1,1)  (1,2,1,1,1)

%e           (4,2)  (1,1,4)  (1,1,3,1)  (1,1,2,1,1)

%e           (2,4)  (3,2,1)  (1,1,1,3)  (1,1,1,2,1)

%e           (3,3)  (3,1,2)  (2,2,1,1)  (1,1,1,1,2)

%e                  (2,3,1)  (2,1,2,1)

%e                  (2,1,3)  (2,1,1,2)

%e                  (1,2,3)  (1,2,2,1)

%e                  (2,2,2)  (1,2,1,2)

%e                           (1,1,2,2)

%e Missing is (1,3,2), reverse of (2,3,1).

%e (End)

%p A189075 := proc(n) local g,i; g := 1; for i from 1 to n do 1-x^i/mul ( 1-x^j,j=i+1..n-i) ; g := g*% ; end do: g := expand(1/g) ; g := taylor(g,x=0,n+1) ; coeftayl(g,x=0,n) ; end proc: # _R. J. Mathar_, Apr 16 2011

%t a[n_] := Module[{g = 1, xi}, Do[xi = 1 - x^i/Product[1 - x^j, {j, i+1, n-i}]; g = g xi, {i, n}]; SeriesCoefficient[1/g, {x, 0, n}]];

%t a /@ Range[0, 32] (* _Jean-François Alcover_, Apr 02 2020, after _R. J. Mathar_ *)

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{___,y_,z_,___,x_,___}/;x<y<z]&]],{n,0,15}] (* _Gus Wiseman_, Aug 19 2024 *)

%Y The non-dashed version is A102726.

%Y The version for 3-12 is A188900, complement A375406.

%Y Avoiding 12-1 also gives A188920 in reverse.

%Y The version for 13-2 is A189077.

%Y For identical leaders we have A374631, ranks A374633.

%Y For distinct leaders we have A374632, ranks A374768.

%Y The complement is counted by A374636, ranks A375137.

%Y A011782 counts compositions.

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

%Y Cf. A056823, A188919, A238343, A274174, A333213, A335480, A358836, A374635.

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Apr 16 2011