A079102 a(2n) = 2^n, a(2n+1) = 2^(2n).

1, 2, 4, 4, 16, 8, 64, 16, 256, 32, 1024, 64, 4096, 128, 16384, 256, 65536, 512, 262144, 1024, 1048576, 2048, 4194304, 4096, 16777216, 8192, 67108864, 16384, 268435456, 32768, 1073741824, 65536, 4294967296, 131072, 17179869184, 262144

Offset

1,2

Comments

The number of permutations of length n containing the minimum number of monotone subsequences of length 3.

Links

Table of n, a(n) for n=1..36.

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

Cf. A079103, A079104, A079105, A079106.

Sequence in context: A064449 A117291 A246047 * A071337 A087481 A038210

Adjacent sequences: A079099 A079100 A079101 * A079103 A079104 A079105

Keyword

easy,nonn

Author

Joseph Myers, Dec 23 2002

Status

approved