A186365 Number of fixed points in all cycle-up-down permutations of {1,2,...,n}.

0, 1, 2, 6, 20, 80, 366, 1904, 11080, 71424, 505210, 3891712, 32433180, 290787328, 2791053734, 28556359680, 310264194320, 3567710830592, 43287834157938, 552688817143808, 7407423764750500, 103981459115606016, 1525675236649033822, 23354749389657604096

Offset

0,3

Comments

A permutation is said to be cycle-up-down if it is a product of up-down cycles. A cycle (b(1), b(2), ...) is said to be up-down if, when written with its smallest element in the first position, it satisfies b(1) < b(2) > b(3) < ..., see example.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

Emeric Deutsch and Sergi Elizalde, Cycle up-down permutations, arXiv:0909.5199 [math.CO], 2009; and also, Australas. J. Combin. 50 (2011), 187-199.

Formula

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

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

a(n) = n*sum(j=0..(n-2)/2, (sum(i=0..(n-2*j-1)/2, (2*i+2*j-n+1)^(n-1)*C(n-2*j-1,i)*(-1)^((n+n-2*j-2)/2-i)))/2^(n-2*j-2)), n>1, a(1)=1, a(0)=0. - Vladimir Kruchinin, May 28 2011

E.g.f.: x/(1-sin(x)).

From Sergei N. Gladkovskii, May 30 2012: (Start)

Let E(x) be the e.g.f., then

E(x) = -1 + 1/(1-x)- x^4/((1-x)*((1-x)*G(0) + x^2)) where G(k)= (2*k+2)*(2*k+3)-x^2+(2*k+2)*(2*k+3)*x^2/G(k+1); (continued fraction, Euler's kind, 1-step).

E(x) = -1 + 1/(1-x)- x^4/((1-x)*((1-x)*G(0) + x^2)) where G(k)= 8*k+6-x^2/(1 + (2*k+2)*(2*k+3)/G(k+1)); (continued fraction, Euler's 2nd kind, 2-step).

E(x) = x/(1-x*G(0)) where G(k)= 1 - x^2/(2*(2*k+1)*(4*k+3) - 2*x^2*(2*k+1)*(4*k+3)/(x^2 - 4*(k+1)*(4*k+5)/G(k+1))); (continued fraction, 3rd kind, 3-step). (End)

E.g.f.: x/(1 - x*G(0)) where G(k)= 1 + x^2/( (2*k+1)*(2*k+3) - 2*k+1)*(2*k+3)^2/(2*k+3 - (2*k+2)/G(k+1))) ; (continued fraction, 3rd kind, 3-step). - Sergei N. Gladkovskii, Oct 01 2012

a(n) ~ n! * 2*n*(2/Pi)^(n+1). - Vaclav Kotesovec, Oct 08 2013

a(n) = n*A000111(n). - Peter Luschny, Oct 27 2017

Recurrence: a(0)=0,a(1)=1, for n > 1, a(n) = Sum_{k=0..floor((n-1)/2)}(-1)^k*binomial(n,2*k+1)*a(n-2*k-1). - Tani Akinari, Nov 01 2017

Example

a(3) = 6 because the cycle-up-down permutations (1)(2)(3), (12)(3), (13)(2), (1)(23), and (132), have a total of 3 + 1 + 1 + 1 + 0 = 6 fixed points.

Maple

g := z/(1-sin(z)): gser := series(g, z = 0, 25):
seq(factorial(n)*coeff(gser, z, n), n = 0 .. 22);
# Alternatively (after Alois P. Heinz):
b := proc(u, o) option remember;
`if`(u + o = 0, 1, add(b(o - 1 + j, u - j), j = 1..u)) end:
a := n -> n*b(n, 0): seq(a(n), n = 0..23); # Peter Luschny, Oct 27 2017

Mathematica

CoefficientList[Series[x/(1-Sin[x]), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 08 2013 *)

Prog

(Maxima)
a(n):=if n<2 then n else n*sum((sum((2*i+2*j-n+1)^(n-1)*binomial(n-2*j-1, i)*(-1)^((n+n-2*j-2)/2-i), i, 0, (n-2*j-1)/2))/2^(n-2*j-2), j, 0, (n-2)/2); (* Vladimir Kruchinin, May 28 2011 *)
(Maxima) a[n]:=if n<2 then n else sum((-1)^k*binomial(n, 2*k+1)*a[n-2*k-1], k, 0, floor((n-1)/2));
makelist(a[n], n, 0, 100); /* Tani Akinari, Nov 01 2017 */
(Sage)
f = x/(1-sin(x))
[factorial(n)*f.series(x, 25).coefficient(x, n) for n in (0..22)]
# Peter Luschny, Jun 26 2012
(Sage)
@CachedFunction
def c(n, k) :
    if n==k: return 1
    if k<1 or k>n: return 0
    return ((n-k)//2+1)*c(n-1, k-1)+k*c(n-1, k+1)
def A186365(n): return n*add(c(n, k) for k in (0..n))
[A186365(n) for n in (0..23)] # Peter Luschny, Jun 10 2014

Crossrefs

Cf. A000111, A186363, A108124.

Sequence in context: A300011 A242154 A108124 * A245373 A204440 A189839

Adjacent sequences: A186362 A186363 A186364 * A186366 A186367 A186368

Keyword

nonn

Author

Emeric Deutsch, Feb 28 2011

Status

approved