Is there any way to count the number of integer partitions of a number $N$ into powers of two such that each size is repeated a power of two times?
Ok, so the recurrence can be expressed by:
$a(0)=1$, $a(2n+1)=a(n)$, $a(2n) = a(n)+a(n-1)+\ldots+a(n-2^m)+\ldots$ $= a(n)+\sum_{i=0}^{\lfloor\log_{2} n\rfloor}a(n-2^i)$
Is there any asymptotic upper bound on this recurrence?
Many Thanks
Here's a relatively easy bound: let $b(n) = \max_{i\leq n }a(i)$. Then we should have $b(2n)\leq \lceil \lg n\rceil b(n)$, so $b(2^k)\leq kb(2^{k-1})$ and $b(2^k)\in O(k!)\in O(k^k) = O(2^{k\lg k})$. This gives a bound of $O(n^{\lg\lg n})$; at first glance it's not clear that this can be improved all the way to a polynomial bound.