A189076 - OEIS

A189076

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

1, 1, 2, 4, 8, 16, 31, 61, 118, 228, 440, 846, 1623, 3111, 5955, 11385, 21752, 41530, 79250, 151161, 288224, 549408, 1047034, 1995000, 3800662, 7239710, 13789219, 26261678, 50012275, 95237360, 181350695, 345315255, 657506300, 1251912618, 2383636280, 4538364446

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..300

S. Heubach, T. Mansour and A. O. Munagi, Avoiding Permutation Patterns of Type (2,1) in Compositions, Online Journal of Analytic Combinatorics, 4 (2009).

Wikipedia, Permutation pattern.

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

EXAMPLE

From Gus Wiseman, Aug 19 2024: (Start)

The a(6) = 31 compositions:

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

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

(4,2) (1,1,4) (1,1,3,1) (1,1,2,1,1)

(2,4) (3,2,1) (1,1,1,3) (1,1,1,2,1)

(3,3) (3,1,2) (2,2,1,1) (1,1,1,1,2)

(2,3,1) (2,1,2,1)

(2,1,3) (2,1,1,2)

(1,2,3) (1,2,2,1)

(2,2,2) (1,2,1,2)

(1,1,2,2)

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

(End)

MAPLE

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

MATHEMATICA

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}]];

a /@ Range[0, 32] (* Jean-François Alcover, Apr 02 2020, after R. J. Mathar *)

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

CROSSREFS

The non-dashed version is A102726.

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

Avoiding 12-1 also gives A188920 in reverse.

The version for 13-2 is A189077.

For identical leaders we have A374631, ranks A374633.

For distinct leaders we have A374632, ranks A374768.

The complement is counted by A374636, ranks A375137.

A011782 counts compositions.

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

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

Sequence in context: A006775 A104993 A223940 * A192656 A128761 A332726