OFFSET
0,4
COMMENTS
a(n) = Theta(2^n), and more precisely, for n >= 4, (13/16)*(3/16)2^n <= a(n) <= (3/16)*2^n.
Indeed, from the formula, one gets a(n) <= (3/16)*2^n, and injecting this in the formula, one gets a(n) >= 2*a(n - 1) - (3/32)*n. Then by induction, and using the formula sum(k*2^k, k = 1 .. n) = (n - 1)*2^(n + 1) + 2, one obtains a(n) >= (13/16)*(3/16)2^n + (3/32)*n + (3/8).
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216, 2015
FORMULA
If n >= 1 is not a power of 2, then a(n) = 2*a(n - 1), and if k >= 1, then a(2^k) = 2*a(2^k - 1) - a(k - 1).
EXAMPLE
a(2) = a(1) = a(0) = 1.
a(3) = a(2) + a(1) = 2.
a(4) = a(3) + a(2) = 3.
a(5) = a(4) + a(3) + a(2) = 6.
PROG
(Haskell)
import Data.List (genericDrop)
a246878 n = a246878_list !! n
a246878_list = 1 : f [1] a000523_list where
f xs (k:ks) = y : f (xs ++ [y]) ks where y = sum $ genericDrop k xs
-- Reinhard Zumkeller, Sep 16 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Benoit Jubin, Sep 06 2014
STATUS
approved