A246015 Number of permutations of n letters that have all valleys even and all peaks odd and that end with an ascent.

0, 1, 1, 3, 4, 34, 70, 853, 2365, 36369, 125870, 2367212, 9829820, 218570717, 1058927507, 27167018427, 150421002736, 4373595961678, 27243141998506, 885304614118777, 6127294825424317, 220074660203753961, 1675478215412320154, 65909583942401516528, 547401364007816870552, 23406034074310130665241

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..470 (first 101 terms from N. J. A. Sloane)

Ira M. Gessel and Yan Zhuang, Counting permutations by alternating descents, arXiv:1408.1886 [math.CO], 2014. See g(n).

Formula

See Maple code for recurrence involving A246012(n) = f(n).

Maple

Gf1:= (3*sin(x/2)+3*cosh(sqrt(3)*x/2))/(3*cos(x/2)-sqrt(3)*sinh(sqrt(3)*x/2));
t1:=series(Gf1, x, 40):
t2:=SERIESTOLISTMULT(t1);
f:=n->t2[n+1]; # this is f(n), A246012
g:=proc(n) global f; option remember; local m, s, k; m:=n-1;
if n=0 then 0 else
s:=add(binomial(m, 2*k)*f(2*k)*(f(m-2*k)-g(m-2*k)), k=0..floor((m-2)/2));
if m mod 2 = 0 then s+f(m) else s+g(m); fi;
fi; end;
[seq(g(n), n=0..30)];
# second Maple program:
b:= proc(u, o, p, t) option remember; `if`(u+o=0, t,
      `if`(t=0 or p=1, add(b(u-j, o+j-1, 1-p, 0), j=1..u), 0)+
      `if`(t=1 or p=0, add(b(u+j-1, o-j, 1-p, 1), j=1..o), 0))
    end:
a:= n-> b(0, n, 0$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 03 2018

Mathematica

f[n_] := SeriesCoefficient[(3*Cosh[(Sqrt[3]*x)/2] + 3*Sin[x/2])/(3*Cos[x/2] - Sqrt[3]*Sinh[(Sqrt[3]*x)/2]), {x, 0, n}]*n!;
g[n_] := g[n] = Module[{m, s, k}, m = n-1; If[n == 0, 0, s = Sum[ Binomial[ m, 2*k]*f[2*k]*(f[m-2*k] - g[m-2*k]), {k, 0, Floor[(m-2)/2]}]; If[EvenQ[m], s + f[m], s + g[m]]]];
Table[g[n], {n, 0, 30}] (* Jean-François Alcover, Jan 23 2018, translated from Maple *)

Crossrefs

Cf. A246012.

Sequence in context: A296250 A032834 A025140 * A078504 A066090 A251259

Adjacent sequences: A246012 A246013 A246014 * A246016 A246017 A246018

Keyword

nonn

Author

N. J. A. Sloane, Aug 11 2014

Status

approved