A097597 Number of permutations of [n] with no increasing runs of even length.

1, 1, 1, 2, 7, 25, 102, 531, 3141, 20218, 146215, 1174889, 10225678, 96226363, 978420285, 10657592850, 123672458583, 1525420453945, 19929519469558, 274771355003651, 3987385414116085, 60764250319690666, 970085750385722631, 16190361659675002857

Offset: 0

Author

Emeric Deutsch, Aug 29 2004

Keywords

• nonn

Examples

			a(4) = 7 because 2/134, 3/124, 4/123, 234/1, 134/2, 124/3 and 4/3/2/1 are the only permutations of [4] with no increasing runs of even length.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..474
• Ira M. Gessel, Generating Functions and Enumeration of Sequences, Ph.D. thesis, MIT, 1977, p. 52.
• Toufik Mansour and Mark Shattuck, A combinatorial proof of a result for permutation pairs, Central European Journal of Mathematics, 10 (2012), 797-806.

Crossrefs

Column k=0 of A097592.

Cf. A000045.

Programs

Maple

G:=sqrt(5)/(sqrt(5)-2*exp(-x/2)*sinh(sqrt(5)*x/2)): Gser:=simplify(series(G,x=0,25)): 1,seq(n!*coeff(Gser,x^n),n=1..24);
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, t,
      add(b(u+j-1, o-j, irem(t+1, 2)), j=1..o)+
      `if`(t=0, 0, add(b(u-j, o+j-1, 1), j=1..u)))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 19 2013

Mathematica

CoefficientList[Series[Sqrt[5]/(Sqrt[5]-2*E^(-x/2)*(E^(Sqrt[5]*x/2)/2 - E^(-Sqrt[5]*x/2)/2)), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Sep 29 2013 *)

Formula

E.g.f.: sqrt(5)/(sqrt(5)-2*exp(-x/2)*sinh(sqrt(5)*x/2)).

E.g.f.: (1 + Sum_{n>=1} (-1)^n F_n x^n/n!)^(-1), where F_n is the n-th Fibonacci number. - Ira M. Gessel, Jul 27 2014

a(n) ~ n! * sinh(r*sqrt(5)) / (2^n*r^(n+1)*(sqrt(5)*cosh(r*sqrt(5))-sinh(r*sqrt(5)))), where r = 0.68903745689226... is the root of the equation 1-exp(-2*sqrt(5)*r) = sqrt(5)*exp((1-sqrt(5))*r). - Vaclav Kotesovec, Sep 29 2013