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

1, 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, 68719476736, 524288

Offset

0,3

Comments

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

Links

Zhuorui He, Table of n, a(n) for n = 0..1000

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.: -(2*x^3+4*x^2-x-1)/((2*x+1)*(2*x-1)*(2*x^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

Extensions

a(0)=1 prepended by Alois P. Heinz, Nov 08 2025

Status

approved