login
Number of alternating patterns of length n.
27

%I #23 Feb 04 2022 18:09:27

%S 1,1,2,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.

%C We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217.

%C A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2). An alternating pattern is necessarily an anti-run (A005649).

%C The version with twins (A344605) is identical to this sequence except with a(2) = 3 instead of 2.

%C From _Gus Wiseman_, Jan 16 2022: (Start)

%C Conjecture: Also the number of weakly up/down patterns of length n, where a sequence is weakly up/down if it is alternately weakly increasing and weakly decreasing, starting with an increase. For example, the a(0) = 1 through a(3) = 6 weakly up/down patterns are:

%C () (1) (1,1) (1,1,1)

%C (2,1) (1,1,2)

%C (2,1,1)

%C (2,1,2)

%C (2,1,3)

%C (3,1,2)

%C (End)

%H Andrew Howroyd, <a href="/A345194/b345194.txt">Table of n, a(n) for n = 0..200</a>

%F a(n) = 2*A350354(n) for n >= 2. - _Andrew Howroyd_, Feb 04 2022

%e The a(0) = 1 through a(3) = 6 alternating patterns:

%e () (1) (1,2) (1,2,1)

%e (2,1) (1,3,2)

%e (2,1,2)

%e (2,1,3)

%e (2,3,1)

%e (3,1,2)

%t wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-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],wigQ]],{n,0,6}]

%o (PARI)

%o F(p,x) = {sum(k=0, p, (-1)^((k+1)\2)*binomial((p+k)\2, k)*x^k)}

%o R(n,k) = {Vec(if(k==1, x, 2*F(k-2,-x)/F(k-1,x)-2-(k-2)*x) + O(x*x^n))}

%o seq(n)= {concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ _Andrew Howroyd_, Feb 04 2022

%Y The version for permutations is A001250, complement A348615.

%Y The version for compositions is A025047, complement A345192.

%Y The version with twins (x,x) is A344605.

%Y The version for perms of prime indices is A345164, complement A350251.

%Y The version for factorizations is A348610, complement A348613, weak A349059.

%Y The weak version is A349058, complement A350138, compositions A349052.

%Y The complement is counted by A350252.

%Y A000670 = patterns, ranked by A333217.

%Y A003242 = anti-run compositions.

%Y A005649 = anti-run patterns, complement A069321.

%Y A019536 = necklace patterns.

%Y A129852 and A129853 = up/down and down/up compositions.

%Y A226316 = patterns avoiding (1,2,3), weakly A052709, complement A335515.

%Y A345170 = partitions w/ alternating permutation, complement A345165.

%Y A349055 = normal multisets w/ alternating permutation, complement A349050.

%Y Cf. A006330, A049774, A128761, A335456, A335457, A335517, A344614, A344615, A345167, A345168.

%K nonn

%O 0,3

%A _Gus Wiseman_, Jun 17 2021

%E a(10)-a(18) from _Alois P. Heinz_, Dec 10 2021

%E Terms a(19) and beyond from _Andrew Howroyd_, Feb 04 2022