login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
OFFSET
0,4
LINKS
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Aug 29 2004
STATUS
approved