cp's OEIS Frontend

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

%I A186365 #70 Feb 12 2025 03:14:10
%S A186365 0,1,2,6,20,80,366,1904,11080,71424,505210,3891712,32433180,290787328,
%T A186365 2791053734,28556359680,310264194320,3567710830592,43287834157938,
%U A186365 552688817143808,7407423764750500,103981459115606016,1525675236649033822,23354749389657604096
%N A186365 Number of fixed points in all cycle-up-down permutations of {1,2,...,n}.
%C A186365 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 A186365 Alois P. Heinz, <a href="/A186365/b186365.txt">Table of n, a(n) for n = 0..300</a>
%H A186365 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 A186365 E.g.f.: z/(1-sin(z)).
%F A186365 a(n) = Sum_{k=0..n} k*A186363(n,k).
%F A186365 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 A186365 E.g.f.: x/(1-sin(x)).
%F A186365 From _Sergei N. Gladkovskii_, May 30 2012: (Start)
%F A186365 Let E(x) be the e.g.f., then
%F A186365 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 A186365 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).
%F A186365 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). (End)
%F A186365 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). - _Sergei N. Gladkovskii_, Oct 01 2012
%F A186365 a(n) ~ n! * 2*n*(2/Pi)^(n+1). - _Vaclav Kotesovec_, Oct 08 2013
%F A186365 a(n) = n*A000111(n). - _Peter Luschny_, Oct 27 2017
%F A186365 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 A186365 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 A186365 g := z/(1-sin(z)): gser := series(g, z = 0, 25):
%p A186365 seq(factorial(n)*coeff(gser, z, n), n = 0 .. 22);
%p A186365 # Alternatively (after _Alois P. Heinz_):
%p A186365 b := proc(u, o) option remember;
%p A186365 `if`(u + o = 0, 1, add(b(o - 1 + j, u - j), j = 1..u)) end:
%p A186365 a := n -> n*b(n, 0): seq(a(n), n = 0..23); # _Peter Luschny_, Oct 27 2017
%t A186365 CoefficientList[Series[x/(1-Sin[x]), {x, 0, 20}], x]* Range[0, 20]! (* _Vaclav Kotesovec_, Oct 08 2013 *)
%o A186365 (Maxima)
%o A186365 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 A186365 (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 A186365 makelist(a[n],n,0,100); /* _Tani Akinari_, Nov 01 2017 */
%o A186365 (Sage)
%o A186365 f = x/(1-sin(x))
%o A186365 [factorial(n)*f.series(x,25).coefficient(x,n) for n in (0..22)]
%o A186365 # _Peter Luschny_, Jun 26 2012
%o A186365 (Sage)
%o A186365 @CachedFunction
%o A186365 def c(n,k) :
%o A186365     if n==k: return 1
%o A186365     if k<1 or k>n: return 0
%o A186365     return ((n-k)//2+1)*c(n-1,k-1)+k*c(n-1,k+1)
%o A186365 def A186365(n): return n*add(c(n,k) for k in (0..n))
%o A186365 [A186365(n) for n in (0..23)] # _Peter Luschny_, Jun 10 2014
%Y A186365 Cf. A000111, A186363, A108124.
%K A186365 nonn
%O A186365 0,3
%A A186365 _Emeric Deutsch_, Feb 28 2011