A350354 Number of up/down (or down/up) patterns of length n.

1, 1, 1, 3, 11, 51, 281, 1809, 13293, 109899, 1009343, 10196895, 112375149, 1341625041, 17249416717, 237618939975, 3491542594727, 54510993341523, 901106621474801, 15723571927404189, 288804851413993941, 5569918636750820751, 112537773142244706427

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. A patten is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase.

A pattern is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. For example, the partition (3,2,2,2,1) has no up/down permutations, even though it does have the anti-run permutation (2,3,2,1,2).

Conjecture: Also the half the number of weakly up/down patterns of length n.

Links

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

Formula

a(n > 2) = A344605(n)/2.

a(n > 1) = A345194(n)/2.

Example

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

Mathematica

allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
updoQ[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], updoQ]], {n, 0, 6}]

Prog

(PARI)
F(p, x) = {sum(k=0, p, (-1)^((k+1)\2)*binomial((p+k)\2, k)*x^k)}
R(n, k) = {Vec(if(k==1, 0, F(k-2, -x)/F(k-1, x)-1) + x + O(x*x^n))}
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

Crossrefs

The version for permutations is A000111, undirected A001250.

For compositions we have A025048, down/up A025049, undirected A025047.

This is the up/down (or down/up) case of A345194.

A000670 counts patterns, ranked by A333217.

A005649 counts anti-run patterns.

A019536 counts necklace patterns.

A226316 counts patterns avoiding (1,2,3), weakly A052709.

A335515 counts patterns matching (1,2,3).

A349058 counts weakly alternating patterns.

A350252 counts non-alternating patterns.

Row sums of A079502.

Cf. A000041, A003242, A049774, A124754, A128761, A335457, A344604, A344605, A344615, A348610.

Sequence in context: A112696 A346967 A192925 * A132006 A367011 A020043

Adjacent sequences: A350351 A350352 A350353 * A350355 A350356 A350357

Keyword

nonn

Author

Gus Wiseman, Jan 16 2022

Extensions

Terms a(10) and beyond from Andrew Howroyd, Feb 04 2022

Status

approved