A137590 Number of alternating full cycles on n letters.

1, 0, 1, 1, 3, 10, 39, 173, 882, 5052, 32163, 225230, 1720635, 14240070, 126917155, 1211969509, 12345020175, 133604426410, 1530993953307, 18518559411876, 235785621577351, 3152221563324450, 44148864630732711, 646438923481545230, 9876859207608319344, 157195096511273995860

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

Table of n, a(n) for n=1..26.

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

Cf. A000111, A129815, A129817.

Sequence in context: A221585 A083862 A205543 * A352174 A124532 A343795

Adjacent sequences: A137587 A137588 A137589 * A137591 A137592 A137593

Keyword

nonn

Author

Vladimir Shevelev, Apr 26 2008

Extensions

More terms from Justin M. Troyka, Jun 11 2015

Status

approved