%I #13 Nov 15 2021 01:17:10
%S 1,1,3,6,22,102,562,3618,26586,219798,2018686,20393790,224750298,
%T 2683250082,34498833434,475237879950,6983085189454,109021986683046,
%U 1802213242949602,31447143854808378,577609702827987882,11139837273501641502,225075546284489412854
%N Number of alternating patterns of length n, including pairs (x,x).
%C 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).
%C An alternating pattern of length > 2 is necessarily an anti-run (A005649).
%C The version without pairs (x,x) is identical to this sequence except a(2) = 2 instead of 3.
%H Martin Ehrenstein, <a href="/A344605/b344605.txt">Table of n, a(n) for n = 0..25</a>
%e The a(0) = 1 through a(4) = 22 patterns:
%e () (1) (1,1) (1,2,1) (1,2,1,2)
%e (1,2) (1,3,2) (1,2,1,3)
%e (2,1) (2,1,2) (1,3,1,2)
%e (2,1,3) (1,3,2,3)
%e (2,3,1) (1,3,2,4)
%e (3,1,2) (1,4,2,3)
%e (2,1,2,1)
%e (2,1,3,1)
%e (2,1,3,2)
%e (2,1,4,3)
%e (2,3,1,2)
%e (2,3,1,3)
%e (2,3,1,4)
%e (2,4,1,3)
%e (3,1,2,1)
%e (3,1,3,2)
%e (3,1,4,2)
%e (3,2,3,1)
%e (3,2,4,1)
%e (3,4,1,2)
%e (4,1,3,2)
%e (4,2,3,1)
%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t Table[Length[Select[Join@@Permutations/@allnorm[n],!MatchQ[#,{___,x_,y_,z_,___}/;x<=y<=z||x>=y>=z]&]],{n,0,6}]
%Y The version for permutations is A001250.
%Y The version for compositions is A344604.
%Y The version for permutations of prime indices is A344606.
%Y A000670 counts patterns (ranked by A333217).
%Y A003242 counts anti-run compositions.
%Y A005649 counts anti-run patterns.
%Y A019536 counts necklace patterns.
%Y A025047 counts alternating or wiggly compositions, complement A345192.
%Y A226316 counts patterns avoiding (1,2,3) (weakly: A052709).
%Y A335515 counts patterns matching (1,2,3).
%Y Cf. A000041, A006330, A049774, A102726, A103919, A124754, A128761, A335456, A335457, A335517, A344612, A344614, A344615, A348377.
%K nonn
%O 0,3
%A _Gus Wiseman_, May 27 2021
%E a(10) and beyond from _Martin Ehrenstein_, Jun 10 2021