A186365 - OEIS

%I #59 Nov 07 2020 06:01:04

%S 0,1,2,6,20,80,366,1904,11080,71424,505210,3891712,32433180,290787328,

%T 2791053734,28556359680,310264194320,3567710830592,43287834157938,

%U 552688817143808,7407423764750500,103981459115606016,1525675236649033822,23354749389657604096

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

%C 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.

%H Alois P. Heinz, <a href="/A186365/b186365.txt">Table of n, a(n) for n = 0..300</a>

%H Emeric Deutsch and Sergi Elizalde, <a href="http://arxiv.org/abs/0909.5199">Cycle up-down permutations</a>, arXiv:0909.5199 [math.CO], 2009; and <a href="https://ajc.maths.uq.edu.au/pdf/50/ajc_v50_p187.pdf">also</a>, Australas. J. Combin. 50 (2011), 187-199.

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

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

%F 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

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

%F From _Sergei N. Gladkovskii_, May 30 2012: (Start)

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

%F 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).

%F 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).

%F 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)

%F 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

%F a(n) ~ n! * 2*n*(2/Pi)^(n+1). - _Vaclav Kotesovec_, Oct 08 2013

%F a(n) = n*A000111(n). - _Peter Luschny_, Oct 27 2017

%F 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

%e 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.

%p g := z/(1-sin(z)): gser := series(g, z = 0, 25):

%p seq(factorial(n)*coeff(gser, z, n), n = 0 .. 22);

%p # Alternatively (after _Alois P. Heinz_):

%p b := proc(u, o) option remember;

%p `if`(u + o = 0, 1, add(b(o - 1 + j, u - j), j = 1..u)) end:

%p a := n -> n*b(n, 0): seq(a(n), n = 0..23); # _Peter Luschny_, Oct 27 2017

%t CoefficientList[Series[x/(1-Sin[x]), {x, 0, 20}], x]* Range[0, 20]! (* _Vaclav Kotesovec_, Oct 08 2013 *)

%o (Maxima)

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

%o (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));

%o makelist(a[n],n,0,100); /* _Tani Akinari_, Nov 01 2017 */

%o (Sage)

%o f = x/(1-sin(x))

%o [factorial(n)*f.series(x,25).coefficient(x,n) for n in (0..22)]

%o # _Peter Luschny_, Jun 26 2012

%o (Sage)

%o @CachedFunction

%o def c(n,k) :

%o     if n==k: return 1

%o     if k<1 or k>n: return 0

%o     return ((n-k)//2+1)*c(n-1,k-1)+k*c(n-1,k+1)

%o def A186365(n): return n*add(c(n,k) for k in (0..n))

%o [A186365(n) for n in (0..23)] # _Peter Luschny_, Jun 10 2014

%Y Cf. A000111, A186363, A108124.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Feb 28 2011