login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137590 Number of alternating full cycles on n letters. 0
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 (list; graph; refs; listen; history; text; internal format)
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 * A124532 A305560 A074728

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 05:01 EDT 2019. Contains 324229 sequences. (Running on oeis4.)