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.
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
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..200
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)
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]]<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
This is the up/down (or down/up) case of A345194.
A205497 are the Euler zig-zag polynomials.
A005649 counts anti-run patterns.
A019536 counts necklace patterns.
A335515 counts patterns matching (1,2,3).
A349058 counts weakly alternating patterns.
A350252 counts non-alternating patterns.
Row sums of A079502.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 16 2022
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Feb 04 2022
STATUS
approved