A006216 Number of down-up permutations of n+4 starting with 4. (Formerly M1466)

2, 5, 14, 46, 178, 800, 4094, 23536, 150178, 1053440, 8057774, 66750976, 595380178, 5688903680, 57975175454, 627692271616, 7195247514178, 87056789995520, 1108708685037134, 14825405274259456, 207676251991176178

Offset

0,1

Comments

Entringer numbers.

References

R. C. Entringer, A combinatorial interpretation of the Euler and Bernoulli numbers, Nieuw Archief voor Wiskunde, 14 (1966), 241-246.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

B. Bauslaugh and F. Ruskey, Generating alternating permutations lexicographically, Nordisk Tidskr. Informationsbehandling (BIT) 30 (1990) 16-26.

J. Millar, N. J. A. Sloane and N. E. Young, A new operation on sequences: the Boustrophedon transform, J. Combin. Theory, 17A (1996) 44-54 (Abstract, pdf, ps).

C. Poupard, De nouvelles significations énumeratives des nombres d'Entringer, Discrete Math., 38 (1982), 265-271.

Formula

a(n) = 3*E(n+2) - E(n), where E(j) = A000111(j) = j!*[x^j](sec(x) + tan(x)) are the up/down or Euler numbers. - Emeric Deutsch, May 15 2004

E.g.f.: 6/(cos(x)*(1 - sin(x))) - tan(x) - 4*sec(x). - Sergei N. Gladkovskii, Jun 04 2015

a(n) ~ 3*n^2 * 2^(n+4) * n! / Pi^(n+3). - Vaclav Kotesovec, Jun 04 2015

Example

a(1) = 5 because we have 41325, 41523, 42314, 42513 and 43512.

Maple

f:=sec(x)+tan(x): fser:=series(f, x=0, 30): E[0]:=1: for n from 1 to 25 do E[n]:=n!*coeff(fser, x^n) od: seq(3*E[n+2]-E[n], n=0..20);

Mathematica

e[0] = e[1] = 1; e[n_] := 2*Sum[ 4^m*Sum[ (i-(n-1)/2)^(n-1)*Binomial[ n-2*m-1, i-m]*(-1)^(n-i-1), {i, m, (n-1)/ 2}], {m, 0, (n-2)/2}]; a[0]=2; a[n_] := 3e[n+2] - e[n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jan 27 2012, after Emeric Deutsch *)

Prog

(PARI) {a(n) = local(v=[1], t); if( n<0, 0, for(k=2, n+4, t=0; v = vector(k, i, if( i>1, t += v[k+1-i]))); v[4])}; /* Michael Somos, Feb 03 2004 */

Crossrefs

Cf. A000111. Column k=3 in A008282.

Sequence in context: A328429 A107268 A231211 * A148337 A149899 A149900

Adjacent sequences: A006213 A006214 A006215 * A006217 A006218 A006219

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved