A186763 Number of increasing odd cycles in all permutations of {1,2,...,n}.

0, 1, 2, 7, 28, 141, 846, 5923, 47384, 426457, 4264570, 46910271, 562923252, 7318002277, 102452031878, 1536780478171, 24588487650736, 418004290062513, 7524077221125234, 142957467201379447, 2859149344027588940, 60042136224579367741

Offset

0,3

Comments

A cycle (b(1), b(2), ...) is said to be increasing if, when written with its smallest element in the first position, it satisfies b(1)<b(2)<b(3)<... .

A cycle is said to be odd if it has an odd number of entries.

Links

Seiichi Manyama, Table of n, a(n) for n = 0..449

Formula

a(n) = Sum_{k>=0} k*A186761(n,k).

E.g.f.: (sinh z)/(1-z).

a(n) ~ n! * (exp(2)-1)*exp(-1)/2. - Vaclav Kotesovec, Oct 05 2013

a(n) = (exp(1)*Gamma(1+n,1) - exp(-1)*Gamma(1+n,-1))/2 = (A000522(n) - A000166(n))/2. - Peter Luschny, Dec 18 2017

a(n) = n! * Sum_{k=0..floor((n-1)/2)} 1 / (2*k+1)!. - Ilya Gutkovskiy, Jul 16 2021

D-finite with recurrence a(n) -n*a(n-1) -a(n-2) +(n-2)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

Example

a(3)=7 because in (1)(2)(3), (1)(23), (12)(3), (13)(2), (123), and (132) we have a total of 3+1+1+1+1+0=7 increasing odd cycles.

Maple

g := sinh(z)/(1-z): gser := series(g, z = 0, 27): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 21);
# Alternatively:
A186763 := n -> (exp(1)*GAMMA(1+n, 1) - exp(-1)*GAMMA(1+n, -1))/2:
seq(simplify(A186763(n)), n=0..21); # Peter Luschny, Dec 18 2017

Mathematica

a=0; Table[a=n*a+(1/2)(1-(-1)^n), {n, 0, 30}] (* Vladimir Joseph Stephan Orlovsky, Apr 02 2011 *)
CoefficientList[Series[Sinh[x]/(1-x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 05 2013 *)

Crossrefs

Cf. A000166, A000522, A009628, A186761, A186762, A186764, A186765, A186766, A186768, A186769, A184958.

Sequence in context: A030875 A130906 A009628 * A182249 A030969 A294531

Adjacent sequences: A186760 A186761 A186762 * A186764 A186765 A186766

Keyword

nonn

Author

Emeric Deutsch, Feb 27 2011

Status

approved