A188920 a(n) is the limiting term of the n-th column of the triangle in A188919.

1, 1, 2, 4, 7, 13, 22, 38, 63, 105, 169, 274, 434, 686, 1069, 1660, 2548, 3897, 5906, 8911, 13352, 19917, 29532, 43605, 64056, 93715, 136499, 198059, 286233, 412199, 591455, 845851, 1205687, 1713286, 2427177, 3428611, 4829563, 6784550, 9505840, 13284849

Offset

0,3

Comments

Also the number of integer compositions of n whose reverse avoids 12-1 and 23-1.

Theorem: The reverse of a composition avoids 12-1 and 23-1 iff its leaders of maximal weakly increasing runs, obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each, are strictly decreasing. For example, the composition y = (4,5,3,2,2,3,1,3,5) has reverse (5,3,1,3,2,2,3,5,4), which avoids 12-1 and 23-1, while the maximal weakly increasing runs of y are ((4,5),(3),(2,2,3),(1,3,5)), with leaders (4,3,2,1), which are strictly decreasing, as required. - Gus Wiseman, Aug 20 2024

Links

John Tyler Rascoe, Table of n, a(n) for n = 0..200

A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.

Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011-2012.

Wikipedia, Permutation pattern.

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

Formula

a(n) = 2^(n-1) - A375140(n).

G.f.: 1 + Sum_{i>0} (B(i,x) * Product_{j=1..i-1} (1 + B(j,x))) where B(i,x) = (x^i)/(1-x^i) * Product_{j>i} (1/(1-x^j)). - John Tyler Rascoe, Aug 23 2024

Example

From Gus Wiseman, Aug 20 2024: (Start)
The a(0) = 1 through a(6) = 22 compositions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)
           (11)  (12)   (13)    (14)     (15)
                 (21)   (22)    (23)     (24)
                 (111)  (31)    (32)     (33)
                        (112)   (41)     (42)
                        (211)   (113)    (51)
                        (1111)  (122)    (114)
                                (212)    (123)
                                (221)    (132)
                                (311)    (213)
                                (1112)   (222)
                                (2111)   (312)
                                (11111)  (321)
                                         (411)
                                         (1113)
                                         (1122)
                                         (2112)
                                         (2211)
                                         (3111)
                                         (11112)
                                         (21111)
                                         (111111)
(End)

Mathematica

b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1, Sum[b[u - j, o + j - 1]*x^(o + j - 1), {j, 1, u}] + Sum[If[u == 0, b[u + j - 1, o - j]*x^(o - j), 0], {j, 1, o}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[0, n]];
Take[T[40], 40] (* Jean-François Alcover, Sep 15 2018, after Alois P. Heinz in A188919 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Greater@@First/@Split[Reverse[#], LessEqual]&]], {n, 0, 15}] (* Gus Wiseman, Aug 20 2024 *)
- or -
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#, {___, y_, z_, ___, x_, ___}/; x<=y<z]&]], {n, 0, 15}] (* Gus Wiseman, Aug 20 2024 *)

Prog

(PARI)
B_x(i, N) = {my(x='x+O('x^N), f=(x^i)/(1-x^i)*prod(j=i+1, N-i, 1/(1-x^j))); f}
A_x(N) = {my(x='x+O('x^N), f=1+sum(i=1, N, B_x(i, N)*prod(j=1, i-1, 1+B_x(j, N)))); Vec(f)}
A_x(60) \\ John Tyler Rascoe, Aug 23 2024

Crossrefs

For leaders of identical runs we have A000041.

Matching 23-1 only gives A189076.

An opposite version is A358836.

For identical leaders we have A374631, ranks A374633.

For distinct leaders we have A374632, ranks A374768.

For weakly increasing leaders we have A374635.


For non-weakly decreasing leaders we have A374636, ranks A375137.

For leaders of anti-runs we have A374680.

For leaders of strictly increasing runs we have A374689.

The complement is counted by A375140, ranks A375295, reverse A375296.

A011782 counts compositions.

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

Cf. A056823, A102726, A188900, A188919, A189077, A238343, A333213, A335480/A335482, A374679, A374688.

Sequence in context: A192758 A085489 A101268 * A281362 A319111 A128768

Adjacent sequences: A188917 A188918 A188919 * A188921 A188922 A188923

Keyword

nonn

Author

N. J. A. Sloane, Apr 13 2011

Extensions

More terms from Andrew Baxter, May 17 2011

a(30)-a(39) from Alois P. Heinz, Nov 14 2015

Status

approved