Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #12 Oct 07 2015 18:08:37
%S 1,2,4,4,16,8,64,16,256,32,1024,64,4096,128,16384,256,65536,512,
%T 262144,1024,1048576,2048,4194304,4096,16777216,8192,67108864,16384,
%U 268435456,32768,1073741824,65536,4294967296,131072,17179869184,262144
%N a(2n) = 2^n, a(2n+1) = 2^(2n).
%C The number of permutations of length n containing the minimum number of monotone subsequences of length 3.
%H Joseph Myers, <a href="http://www.combinatorics.org/Volume_9/Abstracts/v9i2r4.html">The minimum number of monotone subsequences</a>, Electronic J. Combin. 9(2) (2002), #R4.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0, 6, 0, -8).
%F G.f. x(8x^3+2x^2-2x-1)/(2x^2-1)/(4x^2-1). - _Ralf Stephan_, Jul 25 2003
%F 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
%e 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.
%t LinearRecurrence[{0, 6, 0, -8},{1, 2, 4, 4},36] (* _Ray Chandler_, Aug 25 2015 *)
%o (PARI) a(n)=2^if(n%2,n-1,n/2) \\ _Charles R Greathouse IV_, Oct 07 2015
%Y Cf. A079103, A079104, A079105, A079106.
%K easy,nonn
%O 1,2
%A _Joseph Myers_, Dec 23 2002