A349058 Number of weakly alternating patterns of length n.

1, 1, 3, 11, 43, 203, 1123, 7235, 53171, 439595, 4037371, 40787579, 449500595, 5366500163, 68997666867, 950475759899, 13966170378907, 218043973366091, 3604426485899203, 62894287709616755, 1155219405655975763, 22279674547003283003, 450151092568978825707

Offset: 0

Author

Gus Wiseman, Dec 04 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.

Examples

			The a(1) = 1 through a(3) = 11 patterns:
  (1)  (1,1)  (1,1,1)
       (1,2)  (1,1,2)
       (2,1)  (1,2,1)
              (1,2,2)
              (1,3,2)
              (2,1,1)
              (2,1,2)
              (2,1,3)
              (2,2,1)
              (2,3,1)
              (3,1,2)
		

Links

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

Crossrefs

The strict case is A001250, complement A348615.

The strong case of compositions is A025047, ranked by A345167.

The unordered version is A052955.

The strong case is A345194, with twins A344605. Also the directed case.

The version for compositions is A349052, complement A349053.

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

The version for compositions is ranked by A349057.

The version for ordered factorizations is A349059, strong A348610.

The version for partitions is A349060, complement A349061.

A003242 counts Carlitz (anti-run) compositions.

A005649 counts anti-run patterns.

A344604 counts alternating compositions with twins.

A345163 counts normal partitions with an alternating permutation.

A345170 counts partitions w/ an alternating permutation, complement A345165.

A345192 counts non-alternating compositions, ranked by A345168.

A349055 counts multisets w/ an alternating permutation, complement A349050.

Cf. A049774, A096441, A129852, A129853, A336103, A344614, A344615, A344740, A345164, A348613, 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([1], -vector(n,i,1) + 2*sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ) )} \\ Andrew Howroyd, Jan 13 2024

Extensions

a(9)-a(18) from Alois P. Heinz, Dec 10 2021

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