A344605 - OEIS

%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