A344605 Number of alternating patterns of length n, including pairs (x,x).

1, 1, 3, 6, 22, 102, 562, 3618, 26586, 219798, 2018686, 20393790, 224750298, 2683250082, 34498833434, 475237879950, 6983085189454, 109021986683046, 1802213242949602, 31447143854808378, 577609702827987882, 11139837273501641502, 225075546284489412854

Offset

0,3

Comments

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. A sequence is alternating (cf. A025047) including pairs (x,x) if there are no adjacent triples (..., x, y, z, ...) where x <= y <= z or x >= y >= z. These sequences avoid the weak consecutive patterns (1,2,3) and (3,2,1).

An alternating pattern of length > 2 is necessarily an anti-run (A005649).

The version without pairs (x,x) is identical to this sequence except a(2) = 2 instead of 3.

Links

Martin Ehrenstein, Table of n, a(n) for n = 0..25

Example

The a(0) = 1 through a(4) = 22 patterns:
  ()  (1)  (1,1)  (1,2,1)  (1,2,1,2)
           (1,2)  (1,3,2)  (1,2,1,3)
           (2,1)  (2,1,2)  (1,3,1,2)
                  (2,1,3)  (1,3,2,3)
                  (2,3,1)  (1,3,2,4)
                  (3,1,2)  (1,4,2,3)
                           (2,1,2,1)
                           (2,1,3,1)
                           (2,1,3,2)
                           (2,1,4,3)
                           (2,3,1,2)
                           (2,3,1,3)
                           (2,3,1,4)
                           (2,4,1,3)
                           (3,1,2,1)
                           (3,1,3,2)
                           (3,1,4,2)
                           (3,2,3,1)
                           (3,2,4,1)
                           (3,4,1,2)
                           (4,1,3,2)
                           (4,2,3,1)

Mathematica

allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n], !MatchQ[#, {___, x_, y_, z_, ___}/; x<=y<=z||x>=y>=z]&]], {n, 0, 6}]

Crossrefs

The version for permutations is A001250.

The version for compositions is A344604.

The version for permutations of prime indices is A344606.

A000670 counts patterns (ranked by A333217).

A003242 counts anti-run compositions.

A005649 counts anti-run patterns.

A019536 counts necklace patterns.

A025047 counts alternating or wiggly compositions, complement A345192.

A226316 counts patterns avoiding (1,2,3) (weakly: A052709).

A335515 counts patterns matching (1,2,3).

Cf. A000041, A006330, A049774, A102726, A103919, A124754, A128761, A335456, A335457, A335517, A344612, A344614, A344615, A348377.

Sequence in context: A220166 A220167 A243336 * A029848 A366483 A117850

Adjacent sequences: A344602 A344603 A344604 * A344606 A344607 A344608

Keyword

nonn

Author

Gus Wiseman, May 27 2021

Extensions

a(10) and beyond from Martin Ehrenstein, Jun 10 2021

Status

approved