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

Author

Vladimir Shevelev, Apr 26 2008

Keywords

• nonn

Comments

a(n) is the number of full cycles pi of elements 1,2,...,n for which pi(1)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)..., 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

Examples

			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
		

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.

Crossrefs

Cf. A000111, A129815, A129817.

Programs

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

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

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

Extensions

More terms from Justin M. Troyka, Jun 11 2015