A350138 Number of non-weakly alternating patterns of length n.

0, 0, 0, 2, 32, 338, 3560, 40058, 492664, 6647666, 98210192, 1581844994, 27642067000, 521491848218, 10572345303576, 229332715217954, 5301688511602448, 130152723055769810, 3381930236770946120, 92738693031618794378, 2676532576838728227352

Offset: 0

Author

Gus Wiseman, Dec 24 2021

Keywords

• nonn

Comments

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.

We define a sequence to be weakly alternating if it is alternately weakly increasing and weakly decreasing, starting with either.

Conjecture: The directed cases, which count non-weakly up/down or non-weakly down/up patterns, are both equal to the strong case: A350252.

Examples

			The a(4) = 32 patterns:
  (1,1,2,3)  (2,1,1,2)  (3,1,1,2)  (4,1,2,3)
  (1,2,2,1)  (2,1,1,3)  (3,1,2,3)  (4,2,1,3)
  (1,2,3,1)  (2,1,2,3)  (3,1,2,4)  (4,3,1,2)
  (1,2,3,2)  (2,1,3,4)  (3,2,1,1)  (4,3,2,1)
  (1,2,3,3)  (2,3,2,1)  (3,2,1,2)
  (1,2,3,4)  (2,3,3,1)  (3,2,1,3)
  (1,2,4,3)  (2,3,4,1)  (3,2,1,4)
  (1,3,2,1)  (2,4,3,1)  (3,3,2,1)
  (1,3,3,2)             (3,4,2,1)
  (1,3,4,2)
  (1,4,3,2)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200

Crossrefs

The unordered version is A274230, complement A052955.

The strong case of compositions is A345192, ranked by A345168.

The strict case is A348615, complement A001250.

For compositions we have A349053, complement A349052, ranked by A349057.

The complement is counted by A349058.

The version for partitions is A349061, complement A349060.

The version for permutations of prime indices: A349797, complement A349056.

The version for ordered factorizations is A350139, complement A349059.

The strong case is A350252, complement A345194. Also the directed case?

A003242 = Carlitz compositions, complement A261983, ranked by A333489.

A005649 = anti-run patterns, complement A069321.

A025047/A129852/A129853 = alternating compositions, ranked by A345167.

A345163 = normal partitions w/ alternating permutation, complement A345162.

A345170 = partitions w/ alternating permutation, complement A345165.

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

Cf. A049774, A096441, A336103, A344605, A344614, A344615, A344740, A348610, A349794.

Programs

Mathematica

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
whkQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]<=y[[m+1]],y[[m]]>=y[[m+1]]],{m,1,Length[y]-1}];
Table[Length[Select[Join@@Permutations/@allnorm[n],!whkQ[#]&&!whkQ[-#]&]],{n,0,6}]

PARI

R(n,k)={my(v=vector(k,i,1), u=vector(n)); for(r=1, n, if(r%2==0, my(s=v[k]); forstep(i=k, 2, -1, v[i] = s - v[i-1]); v[1] = s); for(i=2, k, v[i] += v[i-1]); u[r]=v[k]); u}
seq(n)= {concat([0], vector(n,i,1) + sum(k=1, n, (vector(n,i,k^i) - 2*R(n, k))*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ) )} \\ Andrew Howroyd, Jan 13 2024

Formula

a(n) = A000670(n) - A349058(n).

Extensions

a(9) onwards from Andrew Howroyd, Jan 13 2024