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

Author

Gus Wiseman, Jan 16 2022

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. 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.

These are the values of the Euler zig-zag polynomials A205497 evaluated at x = 1/2 and normalized by 2^n. - Peter Luschny, Jun 03 2024

Examples

			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)
		

Links

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

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.

A205497 are the Euler zig-zag polynomials.

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.

Programs

Maple

# Using the recurrence by Kyle Petersen from A205497.
G := proc(n) option remember; local F;
if n = 0 then 1/(1 - q*x) else F := G(n - 1);
simplify((p/(p - q))*(subs({p = q, q = p}, F) - subs(p = q, F))) fi end:
A350354 := n -> 2^n*subs({p = 1, q = 1, x = 1/2}, G(n)*(1 - x)^(n + 1)):
seq(A350354(n), n = 0..22);  # Peter Luschny, Jun 03 2024

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

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

Formula

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

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

Extensions

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