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

Author

Ran Pan, Apr 07 2015

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Ran Pan, Exercise Q, Project P

Crossrefs

Cf. A104722, A000111, A000108.

Programs

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

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

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

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.