A137590 - OEIS

%I #21 Jan 23 2019 03:08:31

%S 1,0,1,1,3,10,39,173,882,5052,32163,225230,1720635,14240070,126917155,

%T 1211969509,12345020175,133604426410,1530993953307,18518559411876,

%U 235785621577351,3152221563324450,44148864630732711,646438923481545230,9876859207608319344,157195096511273995860

%N Number of alternating full cycles on n letters.

%C a(n) is the number of full cycles pi of elements 1,2,...,n for which pi(1)<pi(2)>pi(3)<...

%C Calculations show that A000111(n)/n gives a highly good approximation to a(n). Examples: A000111(8)/8=1385/8=173.1 while a(8)=173; A000111(12)/12=225230.4 while a(12)=225230.

%C For all n except 2, a(n) is also the number of full cycles pi of elements 1,2,...,n for which pi(1)>pi(2)<pi(3)>..., although it is not obvious that the number of up-down cycles should be equal to the number of down-up cycles. See the Stanley link. - _Justin M. Troyka_, Jun 11 2015

%H V. Shevelev, <a href="http://arxiv.org/abs/0803.2396">On connection between the numbers of permutations and full cycles with some restrictions on positions and up-down structure</a>, arXiv:0803.2396 [math.CO], 2008-2010.

%H R. P. Stanley, <a href="http://dx.doi.org/10.1016/j.jcta.2006.06.008">Alternating permutations and symmetric functions</a>, J. Combin. Theory Ser. A 114 (2007), 436-460.

%F Write E(n) = A000111(n), the number of alternating permutations on n letters.  If n is odd, then a(n) = (1/n) Sum_{d|n} mu(d) (-1)^{(d-1)/2} E(n/d).  If n is even but not a power of 2, then write n = 2^k m where m is odd, and then a(n) = (1/n) Sum_{d|m} mu(d) E(n/d).  If n is a power of 2 and n >= 4, then a(n) = (1/n) (E(n) - 1).  It follows from these formulas that a(n) ~ E(n)/n.  See the Stanley link. - _Justin M. Troyka_, Jun 11 2015

%e a(3)=1 because we have 231; a(4)=1 because we have 2413; a(5)=3 because we have 24153, 34251, and 45231. - _Emeric Deutsch_, Jul 03 2009

%t t[n_, 0] := If[n==0, 1, 0]; t[n_, k_] := t[n, k] = t[n, k-1] + t[n-1, n-k];

%t e[n_] := t[n, n];

%t a[n_] := If[OddQ[n], (1/n) Sum[MoebiusMu[d] (-1)^((d-1)/2) e[n/d], {d, Divisors[n]}], k = IntegerExponent[n, 2]; m = n/2^k; If[m > 1, (1/n) Sum[ MoebiusMu[d] e[n/d], {d, Divisors[m]}], (1/n)(e[n]-1)]];

%t Array[a, 30] (* _Jean-François Alcover_, Jan 23 2019 *)

%o (PARI) E(n) = if (n<1, n==0, n--; n! * polcoeff( 1 / (1 - sin(x + x * O(x^n))), n));

%o a(n) = if (n % 2, (1/n)*sumdiv(n, d, moebius(d)*(-1)^((d-1)/2)*E(n/d)), k = valuation(n, 2); m = n/2^k; if (m > 1, (1/n)*sumdiv(m, d, moebius(d)*E(n/d)), (1/n)*(E(n) - 1))); \\ _Michel Marcus_, Jun 14 2015

%Y Cf. A000111, A129815, A129817.

%K nonn

%O 1,5

%A _Vladimir Shevelev_, Apr 26 2008

%E More terms from _Justin M. Troyka_, Jun 11 2015