login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A097597 Number of permutations of [n] with no increasing runs of even length. 9
1, 1, 1, 2, 7, 25, 102, 531, 3141, 20218, 146215, 1174889, 10225678, 96226363, 978420285, 10657592850, 123672458583, 1525420453945, 19929519469558, 274771355003651, 3987385414116085, 60764250319690666, 970085750385722631, 16190361659675002857 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 16 11:58 EDT 2021. Contains 345057 sequences. (Running on oeis4.)