login
A350354
Number of up/down (or down/up) patterns of length n.
11
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.
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
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)
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
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.
Sequence in context: A112696 A346967 A192925 * A132006 A367011 A020043
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 16 2022
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Feb 04 2022
STATUS
approved