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,4

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.

Links

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

Formula

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

Example

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)

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}]

Prog

(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

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.

Sequence in context: A091707 A323639 A060868 * A270445 A199019 A127697

Adjacent sequences: A350135 A350136 A350137 * A350139 A350140 A350141

Keyword

nonn

Author

Gus Wiseman, Dec 24 2021

Extensions

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

Status

approved