Subconjuntos cuyo tamaño es un poder de $2$

Question

Un conjunto con $n$ elementos contiene $2^n$ subconjuntos. Lo que si nos restringimos a los subconjuntos cuyo tamaño es una potencia de dos? ¿Esta cantidad se comportan de manera diferente asintóticamente? I. e. ¿cuál es el comportamiento asintótico de:

$$f(n) = \sum_{k=0}^{\lfloor\log{n}\rfloor}\binom{n}{2^k}$$

Answer 1

Como se muestra en los comentarios, es exponencial. Tal vez la mejor manera de describir la asymptotics de una secuencia de examinar la $\limsup$$\liminf$$\frac{1}{n}\log f(n)$.

Vamos a la primera notificación de que $$\max_{k \leq \log n} \binom{n}{2^k} \leq f(n) \leq \log n \max_{k \leq \log n} \binom{n}{2^k}.$$

Esto implica que $$\frac{1}{n} \log f(n) = \frac{1}{n}\max_{k \leq \log n} \log \binom{n}{2^k} + o(1)$$ as $n \to \infty$. Note that this maximum is at most $\log \binom{n}{|n/2|} / n$ which approaches $\log(2)$; moreover, this maximum is achieved along powers of $2$ implying that the $\limsup$ is indeed $2^n$.

El límite inferior no es mucho más difícil: observe que para $n$ en el rango $[2^m, 2^{m+1}]$, el máximo es de los más pequeños en $n = 3\cdot 2^{m-1}$. Estamos por lo tanto interesado en la cantidad $$\lim_{m \to \infty} \frac{1}{3\cdot 2^{m-1}} \log\binom{3 \cdot 2^{m-1}}{2^{m-1}}\,.$$ Applying Stirling's formula shows that the limit along this sequence is $\log(3) - \frac{2}{3}\log(2).$ This shows that $$\limsup_{n \to\infty} \frac{1}{n}\log f(n) = \log(2) \approx .693,\qquad \liminf_{n \to\infty} \frac{1}{n} \log f(n) = \log(3) - \frac{2}{3}\log(2) \approx .637$$