A256644 Numbers of alternating permutations where numbers at odd positions and even positions are monotone respectively.

1, 1, 1, 2, 5, 6, 9, 12, 21, 30, 58, 86, 176, 266, 563, 860, 1861, 2862, 6294, 9726, 21660, 33594, 75584, 117574, 266800, 416026, 950914, 1485802, 3417342, 5348882, 12369287, 19389692, 45052517, 70715342, 165002462, 259289582, 607283492, 955277402, 2244901892

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Ran Pan, Exercise Q, Project P

Formula

For n>3, a(n) = C(floor(n/2))+ C(floor((n-1)/2))+2, where C(n) is the n-th Catalan number, with a(0)=a(1)=a(2)=1 and a(3)=2.

Example

a(5) = 6: (1,3,2,5,4), (1,4,2,5,3), (1,5,2,4,3), (3,4,2,5,1), (3,5,2,4,1), (4,5,2,3,1).
a(6) = 9: (1,3,2,5,4,6), (1,4,2,5,3,6), (1,6,2,5,3,4), (3,4,2,5,1,6), (3,6,2,5,1,4), (4,6,2,5,1,3), (4,6,3,5,1,2), (5,6,2,4,1,3), (5,6,3,4,1,2).

Maple

C:= n-> binomial(2*n, n)/(n+1):
a:= n-> `if`(n<4, [1$3, 2][n+1], C(iquo(n, 2))+C(iquo(n-1, 2))+2):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 08 2015

Mathematica

Table[Which[n < 3, 1, n == 3, 2, True, CatalanNumber[Floor[n/2]] + CatalanNumber[Floor[(n - 1)/2]] + 2], {n, 0, 38}] (* Michael De Vlieger, Apr 07 2015 *)

Prog

(PARI) C(n) = binomial(2*n, n)/(n+1);
a(n) = if (n<3, 1, if (n==3, 2, C(n\2)+ C((n-1)\2)+2)); \\ Michel Marcus, Apr 07 2015
(PARI) a(n) = if (n<4, return(max(1, n-1))); binomial(n\2*2, n\2)/(n\2+1)*if(n%2, 2, (5*n-2)/(4*n-4)) + 2 \\ Charles R Greathouse IV, Apr 07 2015
(Magma) [1, 1, 1, 2] cat [Catalan(Floor(n/2))+ Catalan(Floor((n-1)/2))+2: n in [4..40]]; // Vincenzo Librandi, Apr 08 2015

Crossrefs

Cf. A104722, A000111, A000108.

Sequence in context: A161910 A151920 A160714 * A219764 A286003 A094350

Adjacent sequences: A256641 A256642 A256643 * A256645 A256646 A256647

Keyword

nonn

Author

Ran Pan, Apr 07 2015

Status

approved