OFFSET
1,5
COMMENTS
a(n) is the number of full cycles pi of elements 1,2,...,n for which pi(1)<pi(2)>pi(3)<...
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.
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
LINKS
V. Shevelev, On connection between the numbers of permutations and full cycles with some restrictions on positions and up-down structure, arXiv:0803.2396 [math.CO], 2008-2010.
R. P. Stanley, Alternating permutations and symmetric functions, J. Combin. Theory Ser. A 114 (2007), 436-460.
FORMULA
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
EXAMPLE
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
MATHEMATICA
t[n_, 0] := If[n==0, 1, 0]; t[n_, k_] := t[n, k] = t[n, k-1] + t[n-1, n-k];
e[n_] := t[n, n];
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)]];
Array[a, 30] (* Jean-François Alcover, Jan 23 2019 *)
PROG
(PARI) E(n) = if (n<1, n==0, n--; n! * polcoeff( 1 / (1 - sin(x + x * O(x^n))), n));
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Shevelev, Apr 26 2008
EXTENSIONS
More terms from Justin M. Troyka, Jun 11 2015
STATUS
approved