¿Existe una fórmula en permutaciones y combinaciones si queremos encontrar la suma del número de 1's en la expansión binaria de un número de 1 a n

Question

Se nos da $N$ . Supongamos que $f(x) =$ número de $1$ en la expansión binaria de $x$ . Tenemos que calcular $f(1) +f(2) +f(3)+ \dots +f(N)$ . ¿Existe entonces una fórmula para esta suma directamente en términos de permutaciones y combinaciones?

Gracias de antemano.

Answer 1

Si se calculan los primeros los valores deseados para $N=1,\dots,8$ y presentarlos a Enciclopedia en línea de las secuencias de números enteros el primer retorno es el que se desea: esta secuencia es OEIS A000788 . No aparece ninguna forma cerrada, pero hay una bonita recurrencia. Si $a_n=\sum_{k=0}^nf(k)$ entonces

$$\begin{align*} a_0&=0\;,\\ a_{2n}&=a_n+a_{n-1}+n\;,\text{ and }\\ a_{2n+1}&=2a_n+n+1\;. \end{align*}$$

Para ver por qué $a_{2n}=a_n+a_{n-1}+n$ , tenga en cuenta que $f(2k)=f(k)$ y $f(2k+1)=f(2k)+1=f(k)+1$ para todos $k\in\Bbb N$ . Así,

$$\begin{align*} a_{2n}&=\sum_{k=0}^{2n}f(k)\\ &=\sum_{k=0}^nf(2k)+\sum_{k=0}^{n-1}f(2k+1)\\ &=\sum_{k=0}^nf(k)+\sum_{k=0}^{n-1}\Big(f(k)+1\Big)\\\\ &=a_n+a_{n-1}+n\;. \end{align*}$$

Dejaré la recurrencia para $a_{2n+1}$ a usted; se puede verificar de manera similar.

La entrada de la OEIS da una serie de referencias y varias fórmulas para $a_n$ que implican sumas, así como una función generadora (moderadamente fea).

Answer 2

No es muy difícil de averiguar (¡pero es un poco complicado!) observando que la columna del 1 cambia entre 0 y 1 por cada número, lo que da el techo de N/2 1's, la columna del 2 cambia entre 0 y 1 cada dos números (piensa en cuántos 1's da esto), la columna del 4 cambia entre 0 y 1 cada cuatro números, etc.