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,4

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.

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

Example

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.

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 *)

Crossrefs

Column k=0 of A097592.

Cf. A000045.

Sequence in context: A221457 A221458 A221453 * A150512 A150513 A150514

Adjacent sequences: A097594 A097595 A097596 * A097598 A097599 A097600

Keyword

nonn

Author

Emeric Deutsch, Aug 29 2004

Status

approved