OFFSET
1,2
COMMENTS
The number of permutations of length n containing the minimum number of monotone subsequences of length 3.
LINKS
Joseph Myers, The minimum number of monotone subsequences, Electronic J. Combin. 9(2) (2002), #R4.
Index entries for linear recurrences with constant coefficients, signature (0, 6, 0, -8).
FORMULA
G.f. x(8x^3+2x^2-2x-1)/(2x^2-1)/(4x^2-1). - Ralf Stephan, Jul 25 2003
G.f.: Q(0) where Q(k)= 1 + 2^k*x/(1 - 2*x/(2*x + 2^k/Q(k+1) )); (continued fraction ). - Sergei N. Gladkovskii, Apr 10 2013
EXAMPLE
The permutations of {0,1,2,3,4} containing the minimum number of monotone subsequences of length 3 are 10432, 13042, 13402, 14032, 20413, 20431, 21043, 21403, 23041, 23401, 24013, 24031, 30412, 31042, 31402, 34012, so a(5) = 16. Those of {0,1,2,3,4,5} are 210543, 215043, 240513, 245013, 310542, 315042, 340512, 345012, so a(6) = 8.
MATHEMATICA
LinearRecurrence[{0, 6, 0, -8}, {1, 2, 4, 4}, 36] (* Ray Chandler, Aug 25 2015 *)
PROG
(PARI) a(n)=2^if(n%2, n-1, n/2) \\ Charles R Greathouse IV, Oct 07 2015
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Joseph Myers, Dec 23 2002
STATUS
approved