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
KEYWORD
nonn
AUTHOR
Ran Pan, Apr 07 2015
STATUS
approved